package MinimalBigSum;
import java.io.FileInputStream;
import java.io.PrintStream;
import java.util.Scanner;
public class Solution {
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("input.txt"));
System.setOut(new PrintStream("output.txt"));
Scanner sc = new Scanner(System.in);
int tc = sc.nextInt();
for(int t=1;t<=tc;t++){
int k = sc.nextInt();
int n = sc.nextInt();
int[] a = new int[n];
for(int i=0;i<n;i++){
a[i] = sc.nextInt();
}
System.out.println("#"+t+" "+solution(k,a));
}
}
static int solution(int k,int[] a){
int l = max(a);
int r = sum(a);
while (true){
int mid = (l+r)/2;
int b = blocks(a,mid);
if(b>k){
l = mid+1;
} else if (b<k) {
r = mid-1;
}
else return r;
}
}
static int blocks(int[] a, int mid){
int count = 0;
int sum = a[0];
for (int i = 1; i < a.length; i++) {
if(sum+a[i]>mid){
count++;
sum = a[i];
}
else {
sum+=a[i];
}
}
return count;
}
static int max(int[] a){
int max = -1;
for(int i=0;i<a.length;i++){
if(a[i]>max) max=a[i];
}
return max;
}
static int sum(int[] a){
int sum = 0;
for (int i = 0; i < a.length; i++) {
sum+=a[i];
}
return sum;
}
}
package PointBalance2;
import java.io.FileInputStream;
import java.io.PrintStream;
import java.util.Scanner;
public class Solution {
static int[]x,m;
static int n;
public static void main(String[] args) throws Exception{
System.setIn(new FileInputStream("input.txt"));
System.setOut(new PrintStream("output.txt"));
Scanner sc = new Scanner(System.in);
for(int t=1;t<=2;t++){
n = sc.nextInt();
x = new int[n];
m = new int[n];
for(int i=0;i<n;i++){
x[i] = sc.nextInt();
m[i] = sc.nextInt();
}
int p = f(0,n-1);
// giua x[p] va x[p+1]
System.out.println(p);
}
}
static int f(int left, int right){
if(left>right) return -1;
else if(left+1==right) return left;
else {
int mid = (left+right)/2;
double fl = 0,fr = 0;
for(int i=0;i<mid;i++){
int d = x[mid] - x[i];
fl+= m[i]*0.1/(d*d);
}
for(int i=mid+1;i<n;i++){
int d = x[i]-x[mid];
fr+= m[i]*0.1/d*d;
}
fl = Double.parseDouble(String.format("%.9f", fl));
fr = Double.parseDouble(String.format("%.9f", fr));
if(fl==fr){
return mid;
}
if(fl>fr){
return f(mid+1,right);
}
else {
return f(left, mid+1);
}
}
}
}