分数: 300 点
问题陈述
某编程竞赛网站 AtCode 提供算法问题。 每个问题都会根据其难度分配一个分数。 目前,对于每个整数 i 之间 1 和 D (含),有 p_i 分数为的问题 100i 点。 这些 p_1 + … + p_D 问题是 AtCode 上提供的所有问题。
AtCode 的用户有一个名为 总分。 用户的总分是以下两个要素的总和:
- 基础分数:用户解决的所有问题的分数总和。
- 完美奖励:当用户以 0 分解决所有问题时 100i 积分,他/她获得完美奖金 c_i 分,除基本分数外 (1 ≤ i ≤ D).
AtCode的新用户Takahashi尚未解决任何问题。 他的目标是获得总分 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
在这种情况下,存在三个问题 100 要点和五个问题各有 200 点。解决所有问题的完美奖励 100-点问题是 500 点,以及解决所有问题的完美奖励 200-点问题是 800 点。高桥的目标是总分达到 700 点以上。
实现这一目标的一种方法是解决四个问题 200- 点问题并获得基本分数 800 点。然而,如果我们解决三个 100- 积分问题,我们可以获得完美的奖金 500 基础分数之外的分数 300 分,总分为 800 点,我们就能以更少的问题实现目标。
示例输入 2
2 2000 3 500 5 800
示例输出 2
7
这种情况与样本输入 1 类似,但这次高桥的目标是 2000 点以上。在这种情况下,我们不可避免地需要解决所有五个问题 200-点问题,并通过解决两个 100- 点问题另外我们的总分是 2000 点。
示例输入 3
2 400 3 500 5 800
示例输出 3
2
这种情况再次与样本输入 1 类似,但这次 Takahashi 的目标是 400 点以上。在这种情况下,我们只需要解决两个问题 200-点问题以达到目标。
示例输入 4
5 25000 20 1000 40 1000 50 1000 30 1000 1 1000
示例输出 4
66
只有一个 500- 点问题,但即使在这种情况下也可以获得完美的奖金。