配点
- 満点
- 30
問題文
你正在参加编程比赛。此比赛有 N个问题,每个问题是Pi\(1≤i≤N)个部分问题。 关于第i个问题,j个部分问题时,该问题的得分是s_i_j。
在每个问题中,i个子问题,需要先解决第i-1个子问题。
例如,如果一个问题被设定为有三个子问题,子问题的分数分别为3分、6分、10分的情况下,首先解答第一个子问题可以得到3分,接着解答第二个子问题可以得到6分,解答到第三个子问题时可以得到满分10分(注意,子问题的得分不会累计成总计19分)。
你打算从容易解决的部分开始着手,所以决定按照分值较小的子问题顺序来进行。如果存在分值相同的多个子问题,则优先从题号小的开始解答。
每个子问题所需的时间t_i_j与比赛整体时间T给定时,求在比赛结束前你可以获得多少分。
当比赛结束时间和部分问题解决时间同时发生时,该部分问题也算作已解决。
入力形式
输入采用以下格式给出。
N\ T\\
P_1\ P_2\ …\ P_N\\
s_1_1\ s_1_2\ …\ s_1_{P_1}\\
…\\
s_N_1\ s_N_2\ …\ s_N_{P_N}\\
t_1_1\ t_1_2\ …\ t_1_{P_1}\\
…\\
t_N_1\ t_N_2\ …\ t_N_{P_N}
- N:問題数
- T:比赛时间
- P_i:i第几道题的部分问题数量
- s_i_j:i在第几道题里j解到第几部分问题的总分
- t_i_j:i在第几道题里j解决第几部分问题所需时间
出力形式
输出可获得的积分。
制約
- 1 ≤ N ≤ 20
- 1 ≤ T ≤ 1000
- 1 ≤ P_i ≤ 10
- 1 ≤ s_i_j ≤ 1000, s_i_1< s_i_2< …< s_i_{P_i}
- 1 ≤ t_i_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时比赛结束。
100+150+30 得 280 分。
入力例 2
3 120 1 2 2 100 15 150 30 200 20 10 30 20 40
出力例 2
450
能在规定时间内解出问题3-2。
100+150+200 得 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 的配分相同。
(当然,如果你实际上参加秋季节 2012,可以不遵循此题的规则,按喜欢的顺序解题)
作者: tomerun