Contest Duration: - (local time) (100 minutes) Back to Home
C - All Green /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

プログラミングコンペティションサイト AtCode は、アルゴリズムの問題集を提供しています。 それぞれの問題には、難易度に応じて点数が付けられています。 現在、1 以上 D 以下のそれぞれの整数 i に対して、100i 点を付けられた問題が p_i 問存在します。 これらの p_1 + … + p_D 問が AtCode に収録された問題のすべてです。

AtCode のユーザーは 総合スコア と呼ばれる値を持ちます。 ユーザーの総合スコアは、以下の 2 つの要素の和です。

• 基本スコア: ユーザーが解いた問題すべての配点の合計です。
• コンプリートボーナス: 100i 点を付けられた p_i 問の問題すべてを解いたユーザーは、基本スコアと別にコンプリートボーナス c_i 点を獲得します (1 ≤ i ≤ D)

AtCode の新たなユーザーとなった高橋くんは、まだ問題を 1 問も解いていません。 彼の目標は、総合スコアを G 点以上にすることです。 このためには、少なくとも何問の問題を解く必要があるでしょうか？

制約

• 1 ≤ D ≤ 10
• 1 ≤ p_i ≤ 100
• 100 ≤ c_i ≤ 10^6
• 100 ≤ G
• 入力中のすべての値は整数である。
• c_i, G はすべて 100 の倍数である。
• 総合スコアを G 点以上にすることは可能である。

入力

D G
p_1 c_1
:
p_D c_D


入力例 1

2 700
3 500
5 800


出力例 1

3


この場合、AtCode には 100 点を付けられた問題が 3 問、200 点を付けられた問題が 5 問あります。100 点の 3 問をすべて解いた際のコンプリートボーナスは 500 点、200 点の 5 問をすべて解いた際のコンプリートボーナスは 800 点です。高橋くんの目標は総合スコアを 700 点以上にすることです。

入力例 2

2 2000
3 500
5 800


出力例 2

7


入力例 3

2 400
3 500
5 800


出力例 3

2


ふたたび入力例 1 と似たケースですが、今回の高橋くんの目標は 400 点以上です。この場合、200 点問題を 2 問解くだけで目標を達成できます。

入力例 4

5 25000
20 1000
40 1000
50 1000
30 1000
1 1000


出力例 4

66


500 点の問題が 1 問しか存在しませんが、このような場合でもその問題を解くことでコンプリートボーナスが与えられます。

Score : 300 points

Problem Statement

A programming competition site AtCode provides algorithmic problems. Each problem is allocated a score based on its difficulty. Currently, for each integer i between 1 and D (inclusive), there are p_i problems with a score of 100i points. These p_1 + … + p_D problems are all of the problems available on AtCode.

A user of AtCode has a value called total score. The total score of a user is the sum of the following two elements:

• Base score: the sum of the scores of all problems solved by the user.
• Perfect bonuses: when a user solves all problems with a score of 100i points, he/she earns the perfect bonus of c_i points, aside from the base score (1 ≤ i ≤ D).

Takahashi, who is the new user of AtCode, has not solved any problem. His objective is to have a total score of G or more points. At least how many problems does he need to solve for this objective?

Constraints

• 1 ≤ D ≤ 10
• 1 ≤ p_i ≤ 100
• 100 ≤ c_i ≤ 10^6
• 100 ≤ G
• All values in input are integers.
• c_i and G are all multiples of 100.
• It is possible to have a total score of G or more points.

Input

Input is given from Standard Input in the following format:

D G
p_1 c_1
:
p_D c_D


Output

Print the minimum number of problems that needs to be solved in order to have a total score of G or more points. Note that this objective is always achievable (see Constraints).

Sample Input 1

2 700
3 500
5 800


Sample Output 1

3


In this case, there are three problems each with 100 points and five problems each with 200 points. The perfect bonus for solving all the 100-point problems is 500 points, and the perfect bonus for solving all the 200-point problems is 800 points. Takahashi's objective is to have a total score of 700 points or more.

One way to achieve this objective is to solve four 200-point problems and earn a base score of 800 points. However, if we solve three 100-point problems, we can earn the perfect bonus of 500 points in addition to the base score of 300 points, for a total score of 800 points, and we can achieve the objective with fewer problems.

Sample Input 2

2 2000
3 500
5 800


Sample Output 2

7


This case is similar to Sample Input 1, but the Takahashi's objective this time is 2000 points or more. In this case, we inevitably need to solve all five 200-point problems, and by solving two 100-point problems additionally we have the total score of 2000 points.

Sample Input 3

2 400
3 500
5 800


Sample Output 3

2


This case is again similar to Sample Input 1, but the Takahashi's objective this time is 400 points or more. In this case, we only need to solve two 200-point problems to achieve the objective.

Sample Input 4

5 25000
20 1000
40 1000
50 1000
30 1000
1 1000


Sample Output 4

66


There is only one 500-point problem, but the perfect bonus can be earned even in such a case.