#autumnfest01. [autumn_fest_01]Irregular Contest
[autumn_fest_01]Irregular Contest
配点
满分
30
问题描述
你正在参加一场编程竞赛。这场比赛有N个问题，每个问题被分解为Pi（1≤i≤N）个子问题。对于第i个问题，解决第j个子问题得到的分数是si_j。
对于每个问题，解决第i个子问题需要先解决第i-1个子问题。
例如，某个问题有3个子问题，分数分别为3, 6, 10。如果首先解决第一个子问题，获得3分，然后解决第二个子问题，获得6分，再解决第三个子问题，得到满分10分（注意，子问题的分数不是简单相加的）。
你考虑从最容易的问题开始解决，并按照子问题的配点从小到大的顺序解决。如果有多个配点相同的子问题，则解决问题编号较小的子问题。
给定解决每个子问题所需的时间ti_j 和整个比赛的时间T，求在比赛结束之前你可以获得多少分。
如果比赛结束时间和子问题解决时间相同时，认为该子问题也已解决。
输入格式
输入以以下形式给出：
N T
P1 P2 … PN
s1_1 s1_2 … s1_P1
…
sN_1 sN_2 … sN_PN
t1_1 t1_2 … t1_P1
…
tN_1 tN_2 … tN_PN
- N：问题数
- T：比赛时间
- Pi：第i个问题的子问题数
- si_j：解决第i个问题的前j个子问题时所得的分数
- ti_j：解决第i个问题的第j个子问题所需时间
输出格式
输出获得的总分。
约束条件
- 1 ≤ N ≤ 20
- 1 ≤ T ≤ 1000
- 1 ≤ Pi ≤ 10
- 1 ≤ si_j ≤ 1000，si_1< si_2< …< si_Pi
- 1 ≤ ti_j ≤ 1000
- 输入值为整数。
输入示例 1
3 100
1 2 2
100
15 150
30 200
20
10 30
20 40
输出示例 1
280
按照以下顺序解决：问题2-1（15分）→问题3-1（30分）→问题1-1（100分）→问题2-2（150分）。在解决问题3-2时比赛结束。
总共获得280分。
输入示例 2
3 120
1 2 2
100
15 150
30 200
20
10 30
20 40
输出示例 2
450
刚好在时间结束时解决了问题3-2。
总共获得450分。
输入示例 3
2 100
2 3
15 100
3 100 200
10 90
5 40 40
输出示例 3
18
输入示例 4
3 75
1 1 1
250
500
1000
100
300
1000
输出示例 4
0
输入示例 5
11 300
1 1 2 2 2 3 2 2 2 3 2
30
50
10 60
30 90
20 100
20 40 100
30 110
30 120
40 120
20 40 140
100 150
10
15
10 15
10 20
15 30
15 40 60
40 60
30 50
40 50
10 20 100
100 150
输出示例 5
430
这个例子与Autumn Fest 2012的配分相同。 （当然，如果你实际参加Autumn Fest 2012，不需要按照本题的规则任意解答）
作者：tomerun
题目来源
Autumn Fest