配点

満点

30

問題文

あなたはプログラミングコンテストに参加している。 このコンテストには問題が N問あり、それぞれの問題はPi\（1≤i≤N）個の部分問題に分割されている。i番目の問題について、j個目の部分問題を解くと、その問題の得点はs_i_jになる。

それぞれの問題では、i番目の部分問題を解くにはi-1番目の部分問題を先に解いておく必要がある。

たとえば、ある問題に3つの部分問題が設定されており、部分点が 3点,6点,10点 と指定されている場合、まず1つめの部分問題を解くと3点が得られ、次に2つめを解くと6点、3つめまでを解くと満点の10点が得られる（部分点が加算されて合計19点になるわけではないことに注意）。

あなたは、簡単に解けそうなところから解こうと考え、配点が小さい部分問題から順に取り組んでいくことにした。 同じ配点の部分問題が複数あった場合は、問題番号が小さいものを先に取り組む。

それぞれの部分問題を解くのに必要な時間t_i_jとコンテスト全体の時間Tが与えられたとき、コンテスト終了までにあなたは何点獲得できるかを求めよ。

コンテスト終了時間と部分問題が解けた時間が同時だった場合、その部分問題も解けたものに含める。

入力例 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