#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 20005
int T,n,m,i,j,k,a[MAXN],b[MAXN],r[MAXN],d[MAXN],f[105][MAXN],h[MAXN],ne[MAXN],p[MAXN];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        memset(h,0,sizeof(h));
        scanf("%d%d",&n,&m);
        for(i=2;i<=n;i++)
        {
            scanf("%d",&d[i]);
            d[i]+=d[i-1];
        }
        d[n+1]=2147483647;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d%d",a+i,r+i,b+i);
            j=lower_bound(d+1,d+n+1,d[i]-r[i])-d;
            k=upper_bound(d+1,d+n+1,d[i]+r[i])-d-1;
            p[i]=j;
            ne[i]=h[k];
            h[k]=i;
        }
        for(i=1;i<=n;i++)f[0][i]=f[0][i-1]+b[i];
        for(i=1;i<=m;i++)
        {
            for(j=1;j<=n;j++)for(k=h[j],f[i][j]=f[i][j-1]+b[j];k;k=ne[k])f[i][j]=min(f[i][j],f[i-1][p[k]-1]+a[k]);
            for(j=n-1;j;j--)f[i][j]=min(f[i][j],f[i][j+1]);
        }
        printf("%d\n",f[m][n]);
    }
    return 0;
}