問題文

20XX年、高校教師となったペンギンくんは期末試験の作成に勤しんでいます。

$N$ 個の問題があり、この中から $1$ 問以上を選んで期末試験を作成します。試験時間は $T$ 分と決まっていますが、選ぶ問題の数は自由です。

期末試験はペンギンくんの教え子たちによって解かれますが、その中には太郎くんと次郎くんの $2$ 人がいます。各 $i\ (1 \leq i \leq N)$ について、太郎くんが $i$ 問目の問題を解くのにかかる時間は $A_i$ 分、次郎くんがかかる時間は $B_i$ 分であることが分かっています。

太郎くんを贔屓したいペンギンくんは、なるべく太郎くんに有利になるような試験を作ろうとしています。使用する問題をうまく選ぶことで、（太郎くんが解いた問題数）-（次郎くんが解いた問題数）を最大化してください。

ただし、太郎くん、次郎くんの $2$ 人は各々が試験中に解く問題の数を最大化するように問題を解くこととします。

制約

• $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$ 点) 追加の制約はない

入力例 1Copy

4 8
3 4
5 3
3 4
4 5

出力例 1Copy

1

$1$ 問目と $4$ 問目を選んで試験を作ったとき、太郎くんは $2$ 問、次郎くんは $1$ 問を解きます。

これより（太郎くんが解いた問題数）-（次郎くんが解いた問題数）の値が大きくなる問題の選び方は存在しないので、答えは $1$ となります。

この入力は小課題 $1,4$ の制約を満たします。

入力例 2Copy

6 10
1 2
2 3
2 5
4 7
4 8
5 10

出力例 2Copy

2

この入力はすべての小課題の制約を満たします。

入力例 3Copy

10 100
95 5
85 70
8 44
71 66
74 11
39 2
26 81
29 23
92 70
52 57

出力例 3Copy

2

この入力は小課題 $1,4$ の制約を満たします。

原案: penguinman