配点 : $500$ 点

問題文

高橋君は食べ放題のお店に来ました。

$N$ 種類の料理があり、$i$ 番目の料理は、食べるために $A_i$ 分必要で、美味しさは $B_i$ です。

この店のルールは以下の通りです。

• $1$ 度に $1$ つの料理のみを注文することができます。注文した料理は即座に提供され、食べ始めることができます。
• 同じ種類の料理を $2$ 度以上注文することはできません。
• 提供済みの料理を食べ終わるまで次の料理を注文することはできません。
• 最初の注文から $T-0.5$ 分後以降に注文することはできませんが、提供済みの料理を食べることはできます。

高橋君の満足度を、この来店で高橋君が食べる料理の美味しさの合計とします。

高橋君が適切に行動したとき、満足度は最大でいくらになるでしょうか。

制約

• $2 \leq N \leq 3000$
• $1 \leq T \leq 3000$
• $1 \leq A_i \leq 3000$
• $1 \leq B_i \leq 3000$
• 入力中のすべての値は整数である。

入力

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

$N$ $T$

$A_1$ $B_1$

$:$

$A_N$ $B_N$

出力

高橋君が適切に行動したときの、満足度の最大値を出力せよ。

2 60
10 10
100 100

110

$1$ 番目、$2$ 番目の順に料理を注文することで、満足度は $110$ になります。

注文が時間内に間に合えば、食べるのにどれだけ時間がかかっても良いことに注意してください。

3 60
10 10
10 20
10 30

60

$60$ 分以内に全ての料理を食べることができます。

3 60
30 10
30 20
30 30

50

$2$ 番目、$3$ 番目の順に料理に注文することで、満足度を $50$ にできます。

どのような順に料理を注文しても、料理を $3$ つ注文することはできません。

10 100
15 23
20 18
13 17
24 12
18 29
19 27
23 21
18 20
27 15
22 25

145