コンテスト

問題文

競技プログラミング部 Antsでは $K$ 分間のコンテストが開催される予定です。問題は $N$ 問あり、 $1$ から $N$ まで番号が付けられています。

コンテスト開始から $t$ 分後に問題 $i$ に正解した場合、 $\max (a_i-t \times b_i, 0)$ 点を得ることができます。

部員のmomoyuu君はコンテスト開始前に超能力により、コンテスト中に連続した $t_i$ 分を使うことで問題 $i$ に正解できることが分かりました。正確には、コンテスト開始 $x$ 分後に問題 $i$ を解き始めた場合、 $x+t_i <= K$ であれば問題 $i$ に正解し、 $\max(a_i-(x+t_i) \times b_i, 0)$ 点を得ることができます。momoyuu君は頑固なので一つの問題を解き始めたらその問題に正解するまで他の問題を解き始めることはできません。問題に正解後次の問題を解き始めるまでの時間は考えないものとします。

全ての問題に正解する必要はなく、また問題を好きな順番で解くことができるとき、momoyuu君は最大で何点取ることができますか。一度正解した問題を再び解くことはできないものとします。

制約

• $1 \leq N \leq 2000$
• $1 \leq K \leq 2000$
• $1 \leq t_i \leq 2000 \ (1 \leq i \leq N)$
• $1 \leq a_i, b_i \leq 10^9 \ (1 \leq i \leq N)$
• 入力は全て整数

入力

入力は以下の形式で標準入力で与えられる。

出力

答えを出力せよ。

サンプル

3 10
1 100 10
4 200 20
5 300 30

210

以下のような順番で解くことが最適です。

• コンテスト開始 $0$ 秒後に問題 $1$ を解き始め、コンテスト開始 $1$ 秒後に正解し、 $\max(100-1 \times 10, 0) = 90$ 点得る。
• コンテスト開始 $1$ 秒後に問題 $3$ を解き始め、コンテスト開始 $6$ 秒後に正解し、 $\max(300-6 \times 30, 0) = 120$ 点得る。
• コンテスト開始 $6$ 秒後に問題 $2$ を解き始め、コンテスト開始 $10$ 秒後に正解し、 $\max(200 - 10 \times 20, 0) = 0$ 点得る。

逆に、どのような解き方をしても $210$ 点より多くの得点を得ることはできないため、これが答えとなります。

10 1000
18 7151 183
8 5747 887
13 2522 657
10 6301 273
13 7572 236
94 3647 139
37 7069 347
65 9442 500
39 1205 210
82 9955 218