AT_abc145_e [ABC145E] All-you-can-eat

[problemUrl]: https://atcoder.jp/contests/abc145/tasks/abc145_e 高橋君は食べ放題のお店に来ました。 $ N $ 種類の料理があり、$ i $ 番目の料理は、食べるために $ A_i $ 分必要で、美味しさは $ B_i $ です。 この店のルールは以下の通りです。 - $ 1 $ 度に $ 1 $ つの料理のみを注文することができます。注文した料理は即座に提供され、食べ始めることができます。 - 同じ種類の料理を $ 2 $ 度以上注文することはできません。 - 提供済みの料理を食べ終わるまで次の料理を注文することはできません。 - 最初の注文から $ T-0.5 $ 分後以降に注文することはできませんが、提供済みの料理を食べることはできます。 高橋君の満足度を、この来店で高橋君が食べる料理の美味しさの合計とします。 高橋君が適切に行動したとき、満足度は最大でいくらになるでしょうか。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ T $ $ A_1 $ $ B_1 $ $ : $ $ A_N $ $ B_N $

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

### 制約 - $ 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 $ つ注文することはできません。