← 返回题目列表

AtCoder · pakencamp_2021_day3_d

D. 考试制作

中文机器翻译题面 查看原题

配点 : 600 点

問題文

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 点)无附加约束 打印第

入力

输入是按以下格式从标准输入给出的。

N T
A_1 B_1
A_2 B_2
\hspace{0.6cm}\vdots
A_N B_N

出力

打印(太郎君解决的问题数)-(次郎君解决的问题数)的最大值。


入力例 1

4 8
3 4
5 3
3 4
4 5

出力例 1

1

1 问题和 4 当太郎君选择问题并创建考试时, 2 有问题吗,二郎君? 1 解决问题。

由于无法选择使(太郎君解决的问题数)-(二郎君解决的问题数)的值大于此值的问题,所以答案是 1 。 对于

此输入是一个小作业 1,4 约束。


入力例 2

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

出力例 2

2

此输入满足所有子任务约束。


入力例 3

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

出力例 3

2

此输入是一个小作业 1,4 约束。

原案: 企鹅人