AT_pakencamp_2021_day3_d 試験作り

[problemUrl]: https://atcoder.jp/contests/pakencamp-2021-day3/tasks/pakencamp_2021_day3_d 20XX年、高校教師となったペンギンくんは期末試験の作成に勤しんでいます。 $ N $ 個の問題があり、この中から $ 1 $ 問以上を選んで期末試験を作成します。試験時間は $ T $ 分と決まっていますが、選ぶ問題の数は自由です。 期末試験はペンギンくんの教え子たちによって解かれますが、その中には太郎くんと次郎くんの $ 2 $ 人がいます。各 $ i\ (1\ \leq\ i\ \leq\ N) $ について、太郎くんが $ i $ 問目の問題を解くのにかかる時間は $ A_i $ 分、次郎くんがかかる時間は $ B_i $ 分であることが分かっています。 太郎くんを贔屓したいペンギンくんは、なるべく太郎くんに有利になるような試験を作ろうとしています。使用する問題をうまく選ぶことで、（太郎くんが解いた問題数）-（次郎くんが解いた問題数）を最大化してください。 ただし、太郎くん、次郎くんの $ 2 $ 人は各々が試験中に解く問題の数を最大化するように問題を解くこととします。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ T $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \hspace{0.6cm}\vdots $ $ A_N $ $ B_N $

（太郎くんが解いた問題数）-（次郎くんが解いた問題数）の最大値を出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 1000 $ - $ 1\ \leq\ T\ \leq\ 10000 $ - $ 1\ \leq\ A_i,B_i\ \leq\ T $ - 入力はすべて整数 ### 小課題 1. ($ 50 $ 点) $ N\ \leq\ 16 $ 2. ($ 150 $ 点) すべての $ (i,j) $ について $ A_i\ \lt\ A_j $ ならば $ B_i\ \leq\ B_j $、$ T\ \leq\ 100 $ 3. ($ 150 $ 点) すべての $ (i,j) $ について $ A_i\ \lt\ A_j $ ならば $ B_i\ \leq\ B_j $ 4. ($ 250 $ 点) 追加の制約はない ### Sample Explanation 1 $ 1 $ 問目と $ 4 $ 問目を選んで試験を作ったとき、太郎くんは $ 2 $ 問、次郎くんは $ 1 $ 問を解きます。 これより（太郎くんが解いた問題数）-（次郎くんが解いた問題数）の値が大きくなる問題の選び方は存在しないので、答えは $ 1 $ となります。 この入力は小課題 $ 1,4 $ の制約を満たします。 ### Sample Explanation 2 この入力はすべての小課題の制約を満たします。 ### Sample Explanation 3 この入力は小課題 $ 1,4 $ の制約を満たします。 原案: \[penguinman\](https://atcoder.jp/users/penguinman)