oil_mines_dp_Samsung

#include <iostream>
using namespace std;

int n,c;
int a[10000];
int b[10000];
int pre[1000];
int dp[1000][1000][2];

void solve1(){
    pre[0] = 0;
    for(int i=1; i<=n; i++){
        pre[i] = pre[i-1] + a[i];
    }
}

int solve2(){
    for(int j=1; j<=n; j++){  //mines
        for(int k=1; k<=j && k<=c; k++){ //companies
            if(k==1 || j<=1){
                dp[j][k][0] = pre[j];
                dp[j][k][1] = pre[j];
            }
            else{
                int temp=9999999;
                for(int l=j; l>k-1; l--){
                    int mn = min( (pre[j] - pre[l-1]), min( dp[l-1][k-1][0], dp[l-1][k-1][1]));
                    int mx = max( (pre[j] - pre[l-1]), max( dp[l-1][k-1][0], dp[l-1][k-1][1]));

                    // cout<<" hellp ";
                    if(temp > mx - mn){
                        temp = mx - mn;
                        dp[j][k][0] = mn;
                        dp[j][k][1] = mx;
                    }
                }
            }
        }
    }
    return dp[n][c][1] - dp[n][c][0];
}

int main() {
    int t;
    cin>>t;
    while(t--){
        cin>>c>>n;

        for(int i=1; i<=n; i++) cin>>b[i];

        for(int i=1; i<=n; i++) b[i+n] = b[i];

        int ans=99999;
        for(int i=1; i<=n+1; i++){
            int temp=1;
            for(int k=i; k<i+n; k++){
                a[temp] = b[k];
                temp++;
            }
            solve1();
            ans = min(ans,solve2());
        }
        if(c>n) ans=-1;
        cout<<ans<<endl;
    }
    return 0;
}