Untitled

package Minimal_Big_Sum;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int n, k, result;
	static int[] a;
	
	public static int find(){
		int min = 0, max = 0;
		for(int i = 0; i < n; i++){
			if(a[i] > min){
				min = Math.max(min,a[i]);
			}
			max += a[i];
		}
		int result = max;
		while(min <= max){
			int m = (min + max)/2;
			int block = number(m);
			if(block > k){
				min = m+1;
			}else{
				max = m-1;
				if(m < result){
					result = m;
				}
			}
		}
		return result;
	}
	
	public static int number(int x){
		int count = 1;
//		result = max;
		int sum = 0;
		for(int i = 0; i < n; i++){
			sum += a[i];
			if(sum > x){
				sum = a[i];
				count++;
			}
		}
		return count;
	}
	
	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("input.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
		Scanner scanner = new Scanner(System.in);
		
		int test = scanner.nextInt();
		for(int t = 0; t < test; t++){
			k = scanner.nextInt();
			n = scanner.nextInt();
			a = new int[n];
			for(int i = 0; i < n; i++){
				a[i] = scanner.nextInt();
			}
//			result = 0;
			
//			result  = max;
			
//			System.out.println("find");
			result = find();
			
			System.out.println("#" + (t+1) + " " + result);
		}
		scanner.close();
	}
}