Untitled

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
using namespace std;

#define MAX_A 100000

int T, tc;
int K, N;
int arr[MAX_A];
int lower, upper;
int mid;
int optimal;

int m_sum()
{
	int sum=0;
	for(int i=0; i<N; i++)
	{
		sum+=arr[i];
	}
	return sum;
}

int m_max()
{
	int max=0;
	for(int i=0; i<N; i++)
	{
		max = max > arr[i] ? max : arr[i];
	}
	return max;
}

int count_block(int maxSum)
{
	int cnt=0;
	int sum=arr[0];
	for(int i=1; i<N; i++){
		if(sum+arr[i]>maxSum){
			cnt++;
			sum=arr[i];
		}
		else{
			sum+=arr[i];
		}
	}
	return cnt+1;
}

int main()
{
	freopen("input.txt", "r", stdin);
	cin >> T;
	for(tc=1; tc<=T; tc++)
	{
		cin >> K;
		cin >> N;
		for(int i=0; i<N; i++)
		{
			cin >> arr[i];
		}
		//Solve
		lower=m_max();
		upper=m_sum();
		while(1)
		{
			mid=(lower+upper)/2;
			int block_cnt = count_block(mid);
			if(block_cnt<=K){
				upper = mid;
			} else {
				lower = mid+1;
			}
			if(lower>=upper){
				optimal = upper;
				break;
			}
		}
		cout << "#" << tc << " " << optimal << endl;
	}
	return 0;
}