#include <cstdio>
#include <algorithm>

using namespace std;

const int inf=2e9;

int v[2010],d[2010],minn[2010],aux[2010];

int main()
{
    freopen("antivirus.in","r",stdin);
    freopen("antivirus.out","w",stdout);
    int t,n,k1;
    scanf("%d",&t);
    for(int test=1;test<=t;test++)
    {
        scanf("%d%d",&n,&k1);
        int nr0=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&v[i]);
            if(v[i]==0) nr0++;
        }
        for(int i=1;i<=k1;i++) d[i]=inf;
        int last=0;
        v[n+1]=0;
        for(int i=1;i<=n+1;i++)
            if(v[i]==0)
            {
                int lim=i-last-1,sum=0;
                for(int j=1;j<=lim;j++) minn[j]=inf;
                for(int j=last;j<i;j++)
                {
                    sum+=v[j];
                    int sum1=sum;
                    for(int k=i;k>j;k--)
                    {
                        sum1+=v[k];
                        minn[j-last+i-k]=min(minn[j-last+i-k],sum1);
                    }
                }
                for(int j=1;j<=k1;j++) aux[j]=d[j];
                for(int j=1;j<=lim;j++)
                    for(int k=k1-j;k>=0;k--)
                        if(d[k]<inf) aux[j+k]=min(aux[j+k],d[k]+minn[j]);
                for(int j=1;j<=k1;j++) d[j]=aux[j];
                last=i;
            }
        printf("%d\n",d[k1-nr0]);
    }
    return 0;
}