dp[T][N][K][B]
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std;
#define ll long long
#pragma comment(linker,"/STACK:102400000,102400000")
#define FOR( i, a, b ) for(int i = a; i <= b; ++i )
const int ma=1e+9;
const int fa=1e+3+112;
int n,m,b,k,r,t,T;
int dp[333][333][7][7];
int dp1[7];
int w[333][7];
int x,y,ww;
struct wgh
{
int v,w,t;
int ne;
} ed[fa];
int tot=0,head[fa],tt;
void adde(int x,int y,int t,int w)
{
tot++;
ed[tot].ne=head[x];
ed[tot].v=y;
ed[tot].t=t;
ed[tot].w=w;
head[x]=tot;
}
int main()
{
#ifndef ONLINE_JUDGE
//freopen("out.txt","w",stdout);
//freopen("in.txt","r",stdin);
#endif
int i,j;
scanf("%d",&T);
for(int iii=1; iii<=T; iii++)
{
scanf("%d%d%d%d%d%d",&n,&m,&b,&k,&r,&t);
// for(i=0; i<=t; i++)
// for(j=0; j<=n; j++)
// for(int ii=0; ii<k; ii++)
// for(int jj=0; jj<=b; jj++)
// {
// dp[i][j][ii][jj]=-ma;
// }
memset(dp,-1,sizeof(dp));
dp[0][1][0][0]=r;
for(i=0; i<k; i++)
for(j=1; j<=n; j++)
scanf("%d",&w[j][i]);
tot=0;
memset(head,-1,sizeof(head));
for(i=1; i<=m; i++)
{
scanf("%d%d%d%d",&x,&y,&tt,&ww);
if(x==n)continue;
adde(x,y,tt,ww);
}
for(i=0; i<t; i++)
for(j=1; j<=n; j++)
for(int ii=0; ii<k; ii++)
{
memset(dp1,-1,sizeof(dp1));
for(int jj1=0; jj1<=b; jj1++)
for(int jj2=0; jj2<=b; jj2++)
if(dp[i][j][ii][jj2]>=0)
{
if(w[j][ii]>=0&&(dp[i][j][ii][jj2]-w[j][ii]*(jj1-jj2)>=0))
if(abs(jj1-jj2)<=1)
{
// if(i==2&&j==2&&ii==1&&jj1==1)
// {
// cout<<dp[i][j][ii][jj1]<<endl;
// }
dp1[jj1]=max(dp1[jj1],dp[i][j][ii][jj2]-w[j][ii]*(jj1-jj2));
// if(i==1&&j==2&&ii==0&&jj1==1)
// {
// cout<<dp1[jj1]<<endl;
// }
}
}
for(int jj1=0; jj1<=b; jj1++)
if(dp1[jj1]>=0&&j!=n)
dp[i][j][ii][jj1]=dp1[jj1];
for(int jj=0; jj<=b; jj++)
if(dp[i][j][ii][jj]>=0)
{
// if(i==3&&j==2&&ii==1&&jj==2)
// {
// cout<<dp[i][j][ii][jj]<<endl;
// }
if(j==1||j==n)
if(ii!=0)continue;
//if(j==1&&jj!=0)continue;
if(j==n)
dp[i+1][j][ii][jj]=max(dp[i][j][ii][jj],dp[i+1][j][ii][jj]);
dp[i+1][j][(ii+1+k)%k][jj]=max(dp[i+1][j][(ii+1+k)%k][jj],dp[i][j][ii][jj]);
//dp[i+1][j][(ii-1+k)%k][jj]=max(dp[i+1][j][(ii-1+k)%k][jj],dp[i][j][ii][jj]);
for(int v=head[j]; j!=n&&(~v); v=ed[v].ne)
{
int y=ed[v].v;
int ww=ed[v].w;
int tt=ed[v].t;
//if(y==1)continue;
if(dp[i][j][ii][jj]-ww>=0)
{
if(y==1||y==n)
if(ii!=0)continue;
dp[i+tt][y][ii][jj]=max(dp[i][j][ii][jj]-ww,dp[i+tt][y][ii][jj]);
}
}
}
}
int ans=-ma;
for(i=0; i<=b; i++)
ans=max(ans,dp[t][n][0][i]);
if(ans>=0)
printf("Case #%d: %d\n",iii,ans);
else
printf("Case #%d: Forever Alone\n",iii);
}
return 0;
}
#include <cstdlib>
#i
