E - Making Rope from Materials Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君は、ちょうど W センチメートルの長さのロープを 1 本作る必要があります。

高橋君は N 種類の紐を持っています。i 番目の種類の紐は長さが L_i センチメートルで、C_i 本の在庫があります。異なる種類の紐の長さが同じこともあります。

高橋君は、これらの紐の中から 1 本以上を選び、切断せずにそのままの長さで一直線に繋げてロープを作ります。繋げたロープの長さは、選んだ紐の長さの合計に等しくなります（結び目による長さの減少はありません）。同じ種類の紐を複数本使うこともできますが、i 番目の種類の紐は在庫の C_i 本までしか使えません。

高橋君は、選んだ紐の長さの合計がちょうど 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
  • 1 行目には、紐の種類数を表す N と、作りたいロープの長さを表す W が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各紐の情報が与えられる。
  • 1 + i 行目では、i 番目の種類の紐の長さ L_i と在庫数 C_i が、スペース区切りで与えられる。

出力

ちょうど W センチメートルのロープを作るために必要な紐の最小本数を 1 行で出力してください。ロープを作ることが不可能な場合は、-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

Score : 433 pts

Problem Statement

Takahashi needs to make exactly one rope of exactly W centimeters in length.

Takahashi has N types of strings. The i-th type of string has a length of L_i centimeters, and he has C_i of them in stock. Different types of strings may have the same length.

Takahashi will select one or more of these strings and connect them in a straight line without cutting them, keeping their original lengths, to make a rope. The length of the resulting rope equals the sum of the lengths of the selected strings (there is no length reduction due to knots). He may use multiple strings of the same type, but he can use at most C_i strings of the i-th type.

Takahashi wants to minimize the number of strings used while ensuring that the total length of the selected strings is exactly W centimeters.

If it is possible to make a rope of exactly W centimeters, find the minimum number of strings needed. If it is impossible to make a rope of exactly W centimeters regardless of how the strings are chosen, output -1.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq W \leq 50000
  • 1 \leq L_i \leq W
  • 1 \leq C_i \leq 10000
  • All inputs are integers

Input

N W
L_1 C_1
L_2 C_2
\vdots
L_N C_N
  • The first line contains N, the number of types of strings, and W, the desired length of the rope, separated by a space.
  • From the 2nd line to the (N + 1)-th line, information about each string is given.
  • The (1 + i)-th line contains the length L_i and the stock count C_i of the i-th type of string, separated by a space.

Output

Output in one line the minimum number of strings needed to make a rope of exactly W centimeters. If it is impossible to make the rope, output -1.

Sample Input 1

3 10
3 2
5 3
7 1

Sample Output 1

2

Sample Input 2

2 7
3 2
5 1

Sample Output 2

-1

Sample Input 3

5 80
7 5
13 4
23 3
31 2
50 2

Sample Output 3

3

Sample Input 4

10 5000
3 100
7 200
11 150
19 80
29 60
53 40
97 30
181 20
337 15
631 8

Sample Output 4

12

Sample Input 5

1 1
1 1

Sample Output 5

1