全绿

题目描述

编程竞赛网站 AtCode 提供算法习题集。 每道题都根据难度被赋予相应的分数。 目前,对于每个满足 $1 \le i \le D$ 的整数 $i$,被赋予 $100i$ 分的题有 $p_i$ 道。 这些 $p_1 + … + p_D$ 道题就是 AtCode 收录的全部题目。

AtCode 的用户拥有一个称为「总得分」的值。 用户的总得分是以下两个要素之和。

• 基本得分:用户解出的所有题目的分值之和。
• 全通奖励:解出全部被赋予 $100i$ 分的 $p_i$ 道题的的用户,在基本得分之外,还可获得全通奖励 $c_i$ 分($1 \le i \le D$)。

高桥君成为了 AtCode 的新用户,他还一道题都没有解过。 他的目标是把总得分提升到 $G$ 分及以上。 为此,他至少需要解出多少道题?

输入格式

输入从标准输入按以下格式给出。

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

输出格式

输出为了把总得分提升到 $G$ 分及以上需要解出的最少题目数。该目标必定能够达成(参见数据范围)。

样例

2 700
3 500
5 800

3

这种情况下,AtCode 中有 $3$ 道被赋予 $100$ 分的题和 $5$ 道被赋予 $200$ 分的题。解出全部 $3$ 道 $100$ 分题时的全通奖励是 $500$ 分,解出全部 $5$ 道 $200$ 分题时的全通奖励是 $800$ 分。高桥君的目标是把总得分提升到 $700$ 分及以上。

达成目标的方法之一是解出 $4$ 道 $200$ 分题,获得 $800$ 分基本得分。但是,如果解出全部 $3$ 道 $100$ 分题,在 $300$ 分基本得分之外还会获得 $500$ 分全通奖励,总得分变为 $800$ 分,可以用更少的题目数达成目标。

2 2000
3 500
5 800

7

与样例 1 类似,但这次高桥君的目标是 $2000$ 分及以上。这种情况下,$200$ 分的 $5$ 道题必须全部解出,再解出 $2$ 道 $100$ 分题,总得分即为 $2000$ 分。

2 400
3 500
5 800

2

再次与样例 1 类似,但这次高桥君的目标是 $400$ 分及以上。这种情况下,只需解出 $2$ 道 $200$ 分题即可达成目标。

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

66

虽然 $500$ 分的题只有 $1$ 道,但即使在这种情况下,解出该题也会获得全通奖励。

数据范围

• $1 \le D \le 10$
• $1 \le p_i \le 100$
• $100 \le c_i \le 10^6$
• $100 \le G$
• 输入中的所有值都是整数。
• $c_i, G$ 都是 $100$ 的倍数。
• 把总得分提升到 $G$ 分及以上是可能的。