#include <iostream>
using namespace std;
 
int main() {
	int t;
	cin >> t;
	while(t--)
	{
		int n,k;
		cin>>n>> k;
		int a[k];
		for(int i=0;i<k;i++)
		cin >> a[i];
		int dp[k+1]={0};
		dp[0]=0;
		for(int i=1;i<k+1;i++)
		{
			for(int j=0;j<i;j++)
			{
				if(a[i-1]==-1)
				{
					dp[i]=min(dp[i],dp[j]+dp[i-1-j]);
				}
				else
				{
					dp[i]=a[i-1];
					dp[i]=min(dp[i],dp[j]+dp[i-1-j]);
				}
			}
		}
 
		cout << dp[k]<<endl;
	}
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oKSB7CglpbnQgdDsKCWNpbiA+PiB0OwoJd2hpbGUodC0tKQoJewoJCWludCBuLGs7CgkJY2luPj5uPj4gazsKCQlpbnQgYVtrXTsKCQlmb3IoaW50IGk9MDtpPGs7aSsrKQoJCWNpbiA+PiBhW2ldOwoJCWludCBkcFtrKzFdPXswfTsKCQlkcFswXT0wOwoJCWZvcihpbnQgaT0xO2k8aysxO2krKykKCQl7CgkJCWZvcihpbnQgaj0wO2o8aTtqKyspCgkJCXsKCQkJCWlmKGFbaS0xXT09LTEpCgkJCQl7CgkJCQkJZHBbaV09bWluKGRwW2ldLGRwW2pdK2RwW2ktMS1qXSk7CgkJCQl9CgkJCQllbHNlCgkJCQl7CgkJCQkJZHBbaV09YVtpLTFdOwoJCQkJCWRwW2ldPW1pbihkcFtpXSxkcFtqXStkcFtpLTEtal0pOwoJCQkJfQoJCQl9CgkJfQoJCQoJCWNvdXQgPDwgZHBba108PGVuZGw7Cgl9CglyZXR1cm4gMDsKfQ==

MgozIDUKLTEgLTEgNCA1IC0xCjUgNQoxIDIgMyA0IDUK

2
3 5
-1 -1 4 5 -1
5 5
1 2 3 4 5