 #include <stdio.h>
#include <string.h>
const int N = 105;
int f[N][N][4], v[N][N], r[N][4];
int n, d;
  int max(int a, int b) {
 return a > b ? a : b;
 }
void read() {
memset(v, -1, sizeof(v));
  for(int i = 0; i < n; i ++) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
r[i][1] = a;
r[i][2] = b;
r[i][3] = c;
int m;
scanf("%d", &m);
for(int j = 0; j < m; j ++) {
int t, vv;
scanf("%d %d", &t, &vv);
if( v[i][t] == -1 || v[i][t] < vv)
v[i][t] = vv;
 }
}
}
void floyed() {
for(int i = 0; i < n; i ++) {
for(int j = 0; j < n; j ++) {
for(int k = 0; k < n; k ++) {
if( v[j][i] != -1 && v[i][k] != -1 && (v[j][i] + v[i][k] < v[j][k] || v[j][k] == -1) )
v[j][k] = v[j][i] + v[i][k];
}
}
}
}
void _dp() {
memset(f, -1, sizeof(f));
f[1][0][1] = r[0][1];
for(int i = 2; i < d; i ++) {
for(int j = 0; j < n; j ++) {
for(int k = 0; k < n; k ++) {
for(int t = 1; t <= 3; t ++) {
if( f[i-1][k][t]>=0 && v[k][j]!=-1 && f[i-1][k][t]>=v[k][j] )
f[i][j][1] =max(f[i][j][1], f[i-1][k][t]-v[k][j]+r[j][1]);
}
if(f[i-1][j][1]>=0) f[i][j][2]=max(f[i][j][2], f[i-1][j][1]+r[j][2]);
if(f[i-1][j][2]>=0) f[i][j][3]=max(f[i][j][3], f[i-1][j][2]+r[j][3]);
if(f[i-1][j][3]>=0) f[i][j][3]=max(f[i][j][3], f[i-1][j][3]+r[j][3]);
}
}
}
int ans = 0;
for(int i = 0; i < n; i ++)
for(int j = 1; j <= 3; j ++)
if( ans < f[d-1][i][j] ) ans = f[d-1][i][j];
printf("%d\n", ans);
}
int main() {
while( scanf("%d %d", &n, &d) != EOF) {
read();
floyed();
_dp();
}
}
|