采果子

Grade 0 Open Time Thursday, 11 October 2012, 7:40 am
Discount 0.8 Time Discount Thursday, 11 October 2012, 7:40 am
Allow late Yes Close Time Thursday, 11 October 2012, 7:40 am

【问题描述】
Lyl大牛今天心情不错,于是走到埃及郊外旅游(会不会碰到MMY?...PS:MMY的含义请自行理解)。他边走边向四周望望,发现周围有许多果树。这些树之间互相到达的时间Lyl是知道的(假定每两棵树之间都拥有独立的边可以到达)。他数出了这些果树上果子的个数,并且估了估每个的价格(真是个奇怪的人)。Lyl规定了一种采摘方案,就是对于第i棵树来说,它有a[i]个果子,且所有果子价值为s[i],摘取时间为c[i](小时)。并且,当他摘了第i个树上的果子后,后面他所选择去摘的果树上的果子数必须大于第i棵树上的果子数目,说白了就是一个上升序列;并且每到一棵树,他都必须摘下该树上的所有果子。一开始,Lyl可以在任意一棵树,他只有m小时,那么,在他所拥有的限定时间内,他想知道,这样摘取的最大价值是多少?
【输入文件】
输入文件tree.in第一行2个数:n(表示这条路上的大树数),m(总共时间)
接下来第n+1行,每行三个数a[i],s[i],c[i] (第i+1行输入的为第i颗果树的信息)
且保证有1<=a[i]<=2^31-1;1<=s[1]+s[2]+…+s[n]<=2^31-1;s[i]>=0; 1<=c[i]<=100
接下来的n行,每行n个数,第i行第j个数表示从树i到树j的时间。(0<=T[I,j]<=100;)

【输出文件】
输出文件tree.out有且仅有一个数,即按这样方法摘取的最大价值。
【样例输入】
4 10
1 10 2
2 5 3
3 6 1
4 9 4
0 1 2 3
1 0 3 4
2 3 0 5
3 4 5 0
【样例输出】
21
(先摘第1棵树上的,再摘第2棵树上的,然后第3棵树上的)
【数据范围】
对于60%的数据 ,1<=N<=60,1<=m<=100;
对于100%的数据 ,1<=N<=100, 1<=m<=1000.