AT_pakencamp_2021_day3_d 試験作り

在 20XX 年，Penguin 君成为了一名高中教师，正在努力地准备期末考试。 这次考试中，Penguin 君打算从 $N$ 道题目中挑选出至少一道题来组成试卷。考试时间已定为 $T$ 分钟，不过具体要选多少道题则可以自由决定。 这份试卷将交给两位学生来解答，分别是太郎君和次郎君。已知对于每一道题目 $i\ (1 \leq i \leq N)$，太郎君解决该题需要 $A_i$ 分钟，而次郎君则需要 $B_i$ 分钟。 为了让太郎君在这次考试中占据优势，Penguin 君计划合理选题，使得（太郎君答对的题目数量）减去（次郎君答对的题目数量）的值最大化。 请注意，太郎君和次郎君都会尽量在有限的考试时间内解出最多的题。

输入以以下形式提供： > $N$ $T$ $A_1$ $B_1$ $A_2$ $B_2$ $\cdots$ $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 < A_j$ 则 $B_i \leq B_j$，且 $T \leq 100$ 3. ($150$ 分) 对于所有 $(i, j)$，如果 $A_i < A_j$ 则 $B_i \leq B_j$ 4. ($250$ 分) 没有额外限定条件 ### 样例解释 1 当选取第1题和第4题时，太郎君可以解出2题，而次郎君只能解出1题。这是（太郎君解题数）减去（次郎君解题数）取得最大值的题目选择方式，因此答案为1。这个输入案例满足子任务 1 和 4 的条件。 ### 样例解释 2 这个输入满足所有子任务的条件。 ### 样例解释 3 这个输入满足子任务 1 和 4 的条件。题目原作者：[penguinman](https://atcoder.jp/users/penguinman) **本翻译由 AI 自动生成**