Codechef Birthday Gift

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstring>
using namespace std;
typedef unsigned long long LL;
#define FOR(k,a,b) for(int k(a); k < (b); ++k)
#define FORD(k,a,b) for(int k(a-1); k >= (b); --k)
#define REP(k,a) for(int k=0; k < (a); ++k)
#define ABS(a) ((a)>0?(a):-(a))

int main()
{
#ifdef HOME
    freopen ("in.txt","r",stdin);
    freopen ("out.txt","w",stdout);
#endif
    const int mSize=101;
    const int INF=100000;
    int T,D,n,m,toll[mSize][mSize],C[mSize][mSize],A[mSize][mSize];
    scanf("%d",&T);
    REP(testcase,T)
    {
        scanf("%d %d %d",&D,&n,&m);
        REP(i,m)
            REP(j,n)
            scanf("%d",&(toll[i][j]));
        REP(i,m)
            REP(j,m)
            scanf("%d",&(C[i][j]));
        REP(k,m)
            REP(i,m)
            REP(j,m)
            if(C[i][j]>C[i][k]+C[k][j])
                C[i][j]=C[i][k]+C[k][j];
        REP(i,m)
        {
            A[i][0]=0;
            FOR(j,1,n+1)
                A[i][j]=INF;
        }
        REP(i,n)
        {
            REP(j,m)
            {
                A[j][i+1]=A[j][i]+toll[j][i];
            }
            REP(j,m)
                REP(k,m)
            {
                if(A[j][i+1]>A[k][i+1]+C[k][j])
                    A[j][i+1]=A[k][i+1]+C[k][j];
            }
        }
        int res=A[0][n];
        FOR(i,1,m)
            res=min(res,A[i][n]);
        if(res>D)
            res=-1;
        else
            res=D-res;
        printf("%d\n",res);
    }
    return 0;
}