#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 1000000000
int value[105];
int val[105][105][105],n,k;
bool b_val[105][105][105];
 
int func( int i, int j, int count)
{	//printf("%d %d %d\n",i,j,count);
	if ( i == 0 && count <= n )
	{	//printf("return 0\n");
		return 0;
	}
	if ( j == 0 || count > n )
	{	//printf("return MIN\n");
		return MAX;
	}
	int q1,q2;
	if ( value[j] == -1 )
	{	if ( b_val[i][j-1][count] == 1 )		//skipped here so count-> count only. no +1 here!
			val[i][j][count]= val[i][j-1][count];
		else
			val[i][j][count]= func(i,j-1,count);
		b_val[i][j][count]=1;
		//printf("Return %d\n", val[i][j][count]);
		return val[i][j][count];
	}
	else if ( value[j] > 0 )
	{	if ( b_val[i][j-1][count] == 1 )
			q1=val[i][j-1][count];
		else
			q1= func(i,j-1,count);
		if ( i-j >= 0 )
		{	if ( b_val[i-j][j-1][count+1] == 1 )
				q2= val[i-j][j-1][count+1];
			else
				q2= func(i-j, j-1, count+1)+ value[j];
		}
		else
			q2=MAX;
		//printf("Return %d\n", min(q1,q2));
		b_val[i][j][count]=1;
		return val[i][j][count]= min(q1,q2);
	}
	else if ( value[j] == 0 )			//free so it doesnt need to be bought!
	{	if ( b_val[i][j-1][count] == 1 )
			q1=val[i][j-1][count];
		else
			q1= func(i,j-1,count);
		if ( i- j >= 0 )
		{	if ( b_val[i-j][j-1][count] == 1 )
				q2= val[i-j][j-1][count];
			else
				q2= func(i-j, j-1, count);
		}
		else
			q2=MAX;
		//printf("return %d\n",min(q1,q2));
		b_val[i][j][count]=1;
		return val[i][j][count]= min(q1,q2);
	}
}
 
int main()
{	int t;
	scanf("%d",&t);
	while(t-- > 0 )
	{	//n= rand()%10;
		//k= rand()%10;
		scanf("%d %d",&n,&k);
		//printf("%d %d\n",n,k);
		for ( int i=0; i<105; i++)
			for ( int j=0; j<105; j++)
				for ( int k1=0; k1<105; k1++)
					b_val[i][j][k1]=0;
		for ( int i=1; i<=k; i++)
		{	value[i]= rand()%1000;
			scanf("%d",&value[i]);
			//printf("%d\n",value[i]);
			//value[i]*=-1;
		}
		int p1= func(k,k,0);
		if ( p1 == MAX )
			printf("-1\n");
		else
			printf("%d\n",p1);
	}
	return 0;
}
 

I2luY2x1ZGU8Y3N0ZGlvPgojaW5jbHVkZTxhbGdvcml0aG0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgTUFYIDEwMDAwMDAwMDAKaW50IHZhbHVlWzEwNV07CmludCB2YWxbMTA1XVsxMDVdWzEwNV0sbixrOwpib29sIGJfdmFsWzEwNV1bMTA1XVsxMDVdOwoKaW50IGZ1bmMoIGludCBpLCBpbnQgaiwgaW50IGNvdW50KQp7CS8vcHJpbnRmKCIlZCAlZCAlZFxuIixpLGosY291bnQpOwoJaWYgKCBpID09IDAgJiYgY291bnQgPD0gbiApCgl7CS8vcHJpbnRmKCJyZXR1cm4gMFxuIik7CgkJcmV0dXJuIDA7Cgl9CglpZiAoIGogPT0gMCB8fCBjb3VudCA+IG4gKQoJewkvL3ByaW50ZigicmV0dXJuIE1JTlxuIik7CgkJcmV0dXJuIE1BWDsKCX0KCWludCBxMSxxMjsKCWlmICggdmFsdWVbal0gPT0gLTEgKQoJewlpZiAoIGJfdmFsW2ldW2otMV1bY291bnRdID09IDEgKQkJLy9za2lwcGVkIGhlcmUgc28gY291bnQtPiBjb3VudCBvbmx5LiBubyArMSBoZXJlIQoJCQl2YWxbaV1bal1bY291bnRdPSB2YWxbaV1bai0xXVtjb3VudF07CgkJZWxzZQoJCQl2YWxbaV1bal1bY291bnRdPSBmdW5jKGksai0xLGNvdW50KTsKCQliX3ZhbFtpXVtqXVtjb3VudF09MTsKCQkvL3ByaW50ZigiUmV0dXJuICVkXG4iLCB2YWxbaV1bal1bY291bnRdKTsKCQlyZXR1cm4gdmFsW2ldW2pdW2NvdW50XTsKCX0KCWVsc2UgaWYgKCB2YWx1ZVtqXSA+IDAgKQoJewlpZiAoIGJfdmFsW2ldW2otMV1bY291bnRdID09IDEgKQoJCQlxMT12YWxbaV1bai0xXVtjb3VudF07CgkJZWxzZQoJCQlxMT0gZnVuYyhpLGotMSxjb3VudCk7CgkJaWYgKCBpLWogPj0gMCApCgkJewlpZiAoIGJfdmFsW2ktal1bai0xXVtjb3VudCsxXSA9PSAxICkKCQkJCXEyPSB2YWxbaS1qXVtqLTFdW2NvdW50KzFdOwoJCQllbHNlCgkJCQlxMj0gZnVuYyhpLWosIGotMSwgY291bnQrMSkrIHZhbHVlW2pdOwoJCX0KCQllbHNlCgkJCXEyPU1BWDsKCQkvL3ByaW50ZigiUmV0dXJuICVkXG4iLCBtaW4ocTEscTIpKTsKCQliX3ZhbFtpXVtqXVtjb3VudF09MTsKCQlyZXR1cm4gdmFsW2ldW2pdW2NvdW50XT0gbWluKHExLHEyKTsKCX0KCWVsc2UgaWYgKCB2YWx1ZVtqXSA9PSAwICkJCQkvL2ZyZWUgc28gaXQgZG9lc250IG5lZWQgdG8gYmUgYm91Z2h0IQoJewlpZiAoIGJfdmFsW2ldW2otMV1bY291bnRdID09IDEgKQoJCQlxMT12YWxbaV1bai0xXVtjb3VudF07CgkJZWxzZQoJCQlxMT0gZnVuYyhpLGotMSxjb3VudCk7CgkJaWYgKCBpLSBqID49IDAgKQoJCXsJaWYgKCBiX3ZhbFtpLWpdW2otMV1bY291bnRdID09IDEgKQoJCQkJcTI9IHZhbFtpLWpdW2otMV1bY291bnRdOwoJCQllbHNlCgkJCQlxMj0gZnVuYyhpLWosIGotMSwgY291bnQpOwoJCX0KCQllbHNlCgkJCXEyPU1BWDsKCQkvL3ByaW50ZigicmV0dXJuICVkXG4iLG1pbihxMSxxMikpOwoJCWJfdmFsW2ldW2pdW2NvdW50XT0xOwoJCXJldHVybiB2YWxbaV1bal1bY291bnRdPSBtaW4ocTEscTIpOwoJfQp9CgppbnQgbWFpbigpCnsJaW50IHQ7CglzY2FuZigiJWQiLCZ0KTsKCXdoaWxlKHQtLSA+IDAgKQoJewkvL249IHJhbmQoKSUxMDsKCQkvL2s9IHJhbmQoKSUxMDsKCQlzY2FuZigiJWQgJWQiLCZuLCZrKTsKCQkvL3ByaW50ZigiJWQgJWRcbiIsbixrKTsKCQlmb3IgKCBpbnQgaT0wOyBpPDEwNTsgaSsrKQoJCQlmb3IgKCBpbnQgaj0wOyBqPDEwNTsgaisrKQoJCQkJZm9yICggaW50IGsxPTA7IGsxPDEwNTsgazErKykKCQkJCQliX3ZhbFtpXVtqXVtrMV09MDsKCQlmb3IgKCBpbnQgaT0xOyBpPD1rOyBpKyspCgkJewl2YWx1ZVtpXT0gcmFuZCgpJTEwMDA7CgkJCXNjYW5mKCIlZCIsJnZhbHVlW2ldKTsKCQkJLy9wcmludGYoIiVkXG4iLHZhbHVlW2ldKTsKCQkJLy92YWx1ZVtpXSo9LTE7CgkJfQoJCWludCBwMT0gZnVuYyhrLGssMCk7CgkJaWYgKCBwMSA9PSBNQVggKQoJCQlwcmludGYoIi0xXG4iKTsKCQllbHNlCgkJCXByaW50ZigiJWRcbiIscDEpOwoJfQoJcmV0dXJuIDA7Cn0K

MQo4MyA4Ngo3NzcKOTE1Cjc5MwozMzUKMzg2CjQ5Mgo2NDkKNDIxCjM2MgoyNwo2OTAKNTkKNzYzCjkyNgo1NDAKNDI2CjE3Mgo3MzYKMjExCjM2OAo1NjcKNDI5Cjc4Mgo1MzAKODYyCjEyMwo2NwoxMzUKOTI5CjgwMgoyMgo1OAo2OQoxNjcKMzkzCjQ1NgoxMQo0MgoyMjkKMzczCjQyMQo5MTkKNzg0CjUzNwoxOTgKMzI0CjMxNQozNzAKNDEzCjUyNgo5MQo5ODAKOTU2Cjg3Mwo4NjIKMTcwCjk5NgoyODEKMzA1CjkyNQo4NAozMjcKMzM2CjUwNQo4NDYKNzI5CjMxMwo4NTcKMTI0Cjg5NQo1ODIKNTQ1CjgxNAozNjcKNDM0CjM2NAo0Mwo3NTAKODcKODA4CjI3NgoxNzgKNzg4CjU4NAo0MDMKNjUx

1
83 86
777
915
793
335
386
492
649
421
362
27
690
59
763
926
540
426
172
736
211
368
567
429
782
530
862
123
67
135
929
802
22
58
69
167
393
456
11
42
229
373
421
919
784
537
198
324
315
370
413
526
91
980
956
873
862
170
996
281
305
925
84
327
336
505
846
729
313
857
124
895
582
545
814
367
434
364
43
750
87
808
276
178
788
584
403
651