题目描述

プログラミングコンペティションサイト 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$ 点以上にすることです。 このためには、少なくとも何問の問題を解く必要があるでしょうか？

输入格式

入力は以下の形式で標準入力から与えられる。

$D$ $G$ $p_1$ $c_1$ $:$ $p_D$ $c_D$

输出格式

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

题目大意

有 $D$ 套题目，难度从 $1$ 到 $D$ ，第 $i$ 套题目有 $p_i$ 道，分值均为 $i \times 100$，全部做完再奖励 $c_i$ 分，求至少拿到 $G$ 分至少要刷多少道题？

2 700
3 500
5 800

3

2 2000
3 500
5 800

7

2 400
3 500
5 800

2

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

66

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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

Sample Explanation 3

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

Sample Explanation 4

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