分数: 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