题目描述

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

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

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

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

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

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

输入格式

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

$N$ $T$ $A_1$ $B_1$ $:$ $A_N$ $B_N$

输出格式

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

题目大意

有$n$道菜，每道菜需要$a[i]$分吃完，能获得$b[i]$的美味值 给$T$分钟，问怎么样吃，才能在$T$内得到最多的美味值，

一旦开始了吃就一定会吃完这道菜，哪怕时间超过$T$分

2 60
10 10
100 100

110

3 60
10 10
10 20
10 30

60

3 60
30 10
30 20
30 30

50

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

145

提示

制約

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

Sample Explanation 1

$1$ 番目、$2$ 番目の順に料理を注文することで、満足度は $110$ になります。 注文が時間内に間に合えば、食べるのにどれだけ時間がかかっても良いことに注意してください。

Sample Explanation 2

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

Sample Explanation 3

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