All Green

题目描述

一家编程竞赛网站 AtCode 提供算法题目。 每道题根据难度被分配一个分数。 目前，对于每个整数 $i$，$1$ 到 $D$（含），有 $p_i$ 道题目的分数为 $100i$ 分。 这些 $p_1 + … + p_D$ 道题目就是 AtCode 上所有可做的题目。 AtCode 的用户有一个称为 总分 的值。 用户的总分是以下两部分之和：

基础分：用户所做题目的分数之和。 满分奖：当用户把所有分数为 $100i$ 分的题目都做完时，除了基础分外，他/她还可以获得 $c_i$ 分的满分奖（$1 ≤ i ≤ D$）。

刚加入 AtCode 的高桥（Takahashi）还没有做任何题。 他的目标是使总分达到至少 $G$ 分。 为此至少需要做多少道题？

输入格式

输入按照下列格式从标准输入给出： $D$ $G$ $p_1$ $c_1$ $:$ $p_D$ $c_D$

输出格式

输出为了使总分达到至少 $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$ 分。在这个例子中，有三道 $100$ 分的题和五道 $200$ 分的题。做完所有 $100$ 分题的满分奖是 $500$ 分，做完所有 $200$ 分题的满分奖是 $800$ 分。高桥的目标是使总分达到至少 $700$ 分。 一种可行的方法是做四道 $200$ 分题，获得 $800$ 分的基础分。然而，如果我们做完三道 $100$ 分题，就可以在 $300$ 分的基础分之外再获得 $500$ 分的满分奖，总分为 $800$ 分，并且可以用更少的题数达成目标。
这个例子与样例输入 1 类似，但这次高桥的目标是至少 $2000$ 分。在这种情况下，我们不可避免地需要做完所有五道 $200$ 分题，并且再做两道 $100$ 分题就可以得到 $2000$ 分的总分。
这个例子又与样例输入 1 类似，但这次高桥的目标是至少 $400$ 分。在这种情况下，我们只需做两道 $200$ 分题就可以达成目标。
只有一道 $500$ 分的题，但即便在这种情况下也可以获得满分奖。

标签: AtCoder|abc104C

来源

AtCoder|abc104C