#include <bits/stdc++.h>
using namespace std; 

main(){
    int t ; 
    cin >> t ;
    while(t--){
    long long n , k ;
    cin >> k >> n;
    
    vector<long long> arr(n) ;
    
    for(int i = 0; i < n; ++i)cin >> arr[i] ; 

    
    long long s = *max_element(arr.begin(), arr.end()), e = (n)**max_element(arr.begin(), arr.end()) ;
    
    for(int i = 1; i <= n - 1; ++i){
        arr[i] += arr[i-1] ;
    }
    
    while(e > s){
        long long mid = s + (e-s) / 2 ;
        
        long long sum = 0 ;
        bool fff = false ;
        for(int i = 0; i < k; ++i){
            auto it = upper_bound(arr.begin(), arr.end(), sum + mid) ;
            if(it == arr.end()){
                fff = true ;
                break ;
            }
            if(it == arr.begin())break ;
            sum -= *(--it) ;
            if(sum == 0)break ;
            sum = *it ;
        }
        
        if(fff)e = mid ;
        else s = mid + 1 ;
        
    }
    
    cout << e << "\n" ;
    }
    
}