C - All Green

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300

問題文

プログラミングコンペティションサイト 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

出力

総合スコアを G 点以上にするために解く必要のある最小の問題数を出力せよ。なお、この目標は必ず達成可能である(制約を参照のこと)。


入力例 1

2 700
3 500
5 800

出力例 1

3

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

目標を達成する方法の一つは、200 点問題を 4 問解いて 800 点の基本スコアを得ることです。しかし、100 点問題を 3 問すべて解くと、基本スコア 300 点に加えてコンプリートボーナスの 500 点が与えられて総合スコアが 800 点となり、より少ない問題数で目標を達成することができます。


入力例 2

2 2000
3 500
5 800

出力例 2

7

入力例 1 と似たケースですが、今回の高橋くんの目標は 2000 点以上です。この場合、200 点の 5 問は必ずすべて解かなければならず、さらに 100 点問題を 2 問解くことで総合スコアが 2000 点となります。


入力例 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.