コンテスト

2 secs 1024 MB
momoyuu's icon momoyuu

問題文

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

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

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

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

制約

  • 1N20001 \leq N \leq 2000
  • 1K20001 \leq K \leq 2000
  • 1ti2000 (1iN)1 \leq t_i \leq 2000 \ (1 \leq i \leq N)
  • 1ai,bi109 (1iN)1 \leq a_i, b_i \leq 10^9 \ (1 \leq i \leq N)
  • 入力は全て整数

入力

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

NNKK
t1t_1a1a_1b1b_1
t2t_2a2a_2b2b_2
\vdots
tNt_NaNa_NbNb_N

出力

答えを出力せよ。

サンプル

入力例1
3 10
1 100 10
4 200 20
5 300 30
出力例1
210

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

  • コンテスト開始 00 秒後に問題 11 を解き始め、コンテスト開始 11 秒後に正解し、 max(1001×10,0)=90\max(100-1 \times 10, 0) = 90 点得る。
  • コンテスト開始 11 秒後に問題 33 を解き始め、コンテスト開始 66 秒後に正解し、 max(3006×30,0)=120\max(300-6 \times 30, 0) = 120 点得る。
  • コンテスト開始 66 秒後に問題 22 を解き始め、コンテスト開始 1010 秒後に正解し、 max(20010×20,0)=0\max(200 - 10 \times 20, 0) = 0 点得る。

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

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

5982

Submit


Go (1.21)