分数: 433 分
问题陈述
高桥需要制作一根绳子 W 厘米长。
高桥有 N 字符串类型。的 i- 字符串类型的长度为 L_i 厘米,他有 C_i 其中有库存。不同类型的字符串可能具有相同的长度。
高桥将选择一根或多根这些绳子,并将它们连接成一条直线,而不切割它们,保持其原始长度,以制成一根绳子。所得绳索的长度等于所选绳索长度的总和(不会因结而减少长度)。他可能会使用多个相同类型的字符串,但他最多可以使用 C_i 的字符串 i第类型。
Takahashi 希望最大限度地减少所使用的字符串数量,同时确保所选字符串的总长度恰好为 W 厘米。
如果可以精确地制作一根绳子 W 厘米,求所需的最少绳数。如果不可能准确地制作一根绳子 W 厘米无论如何选择字符串,输出 -1.
约束
- 1 \leq N \leq 100
- 1 \leq W \leq 50000
- 1 \leq L_i \leq W
- 1 \leq C_i \leq 10000
- 所有输入均为整数
输入
N W L_1 C_1 L_2 C_2 \vdots L_N C_N
- 第一行包含 N,字符串类型的数量,以及 W,所需的绳索长度,以空格分隔。
- 从第 2 行到 (N + 1)第行,给出了每个字符串的信息。
- 的 (1 + i)第行包含长度 L_i 和库存数量 C_i 的 i- 字符串类型,以空格分隔。
输出
在一行中输出制作一根绳子所需的最少绳数 W 厘米。如果无法制作绳子,则输出 -1.
示例输入 1
3 10 3 2 5 3 7 1
示例输出 1
2
示例输入 2
2 7 3 2 5 1
示例输出 2
-1
示例输入 3
5 80 7 5 13 4 23 3 31 2 50 2
示例输出 3
3
示例输入 4
10 5000 3 100 7 200 11 150 19 80 29 60 53 40 97 30 181 20 337 15 631 8
示例输出 4
12
示例输入 5
1 1 1 1
示例输出 5
1