/ 
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.