← 返回题目列表

AtCoder · awc0085_e

E. 最大限度地减少播放列表中的类型不平衡

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

分数: 433 分

问题陈述

Takahashi 正在尝试创建一个播放列表 2N 候选歌曲。

的 树的 i第首歌曲 (1 \leq i \leq 2N) 属于流派 B_i 并且持续时间为 A_i 秒。

Takahashi 从候选者中选择一首或多首歌曲(每首歌曲最多只能选择一次),并按照他喜欢的任何顺序排列它们以创建播放列表。

但是,所选歌曲的总时长必须至少为 K 秒。

在创建的播放列表中,所有歌曲属于同一流派的连续片段中包含的歌曲的最大数量称为“偏差分数”。

更准确地说,考虑播放列表中歌曲的所有连续子序列,使得每个子序列中的所有歌曲都属于同一流派;偏差分数是所有此类子序列中歌曲的最大数量。

在所有可能的选择和排列满足条件的歌曲的方法中,找到最小可能的偏差分数。

如果总持续时间小于 K 秒即使选择了所有歌曲,因此无法满足条件,输出 -1.

约束

  • 1 \leq N \leq 150
  • 1 \leq K \leq 10^9
  • 1 \leq B_i \leq 2N
  • 1 \leq A_i \leq 10^6
  • 所有输入值均为整数

输入

N K
B_1 A_1
B_2 A_2
\vdots
B_{2N} A_{2N}
  • 第一行包含一个整数 N 代表候选歌曲数量的一半,一个整数 K 表示总持续时间的下限,以空格分隔。
  • 如下 2N 行, i第行 (1 \leq i \leq 2N) 包含流派 B_i 和持续时间 A_i 的 i第首歌曲,以空格分隔。

输出

在一行中输出可能的最小偏差分数。如果无法选择满足条件的歌曲,则输出 -1.


示例输入 1

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

示例输出 1

1

示例输入 2

2 31
1 8
2 7
2 6
3 9

示例输出 2

-1

示例输入 3

8 120
1 15
1 12
2 20
2 7
3 9
3 18
4 25
5 5
5 14
6 11
7 30
7 6
8 10
9 16
10 8
10 13

示例输出 3

1

示例输入 4

20 650
1 45
1 32
1 28
2 60
2 15
3 22
3 48
4 35
4 40
5 10
5 55
6 70
6 18
7 25
7 27
8 80
9 12
9 44
10 33
10 36
11 90
12 14
12 29
13 50
13 52
14 20
15 65
15 17
16 31
16 39
17 75
18 11
18 24
19 46
20 58
21 13
22 41
23 30
24 62
25 19

示例输出 4

1

示例输入 5

1 2
1 1
1 1

示例输出 5

2