← 返回题目列表

AtCoder · awc0024_e

E. 用材料制作绳索

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

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