Untitled

#include <iostream>

using namespace std;

int a[100001], n, k;

void solve(int index) {
	cin >> k >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int sum = 0, max = 0, top = 0, pv = 0, maxSum = 0, result = 0;
	for (int i = 0; i < n; i++) {
		sum += a[i];
		if (a[i] > max)	max = a[i];
	}
	if (k > 1) {
		top = (sum + max) / 2;
		maxSum = sum;
		while (pv <= k) {
			top = (maxSum + max) / 2;
			pv = 0;
			sum = 0;
			maxSum = 0;
			for (int i = 0; i < n; i++) {
				sum += a[i];
				if (sum > top) {
					sum -= a[i];
					pv++;
					if (sum > maxSum)	maxSum = sum;
					sum = 0;
					sum += a[i];
				}
			}
			pv++;
			if (pv <= k) {
				if (sum > maxSum)	maxSum = sum;
				if (result == maxSum) {
					break;
				}
				result = maxSum;
			}
		}
		cout << result << endl;
	}
	else {
		cout << sum << endl;
	}
}

int main() {
	int t;
	cin >> t;
	for (int i = 1; i <= t; i++) {
		solve(i);
	}
}