AT_abc104_c [ABC104C] All Green

题目描述

编程竞赛网站 AtCode 提供了一套算法题集。每道题目根据难度被赋予了不同的分数。对于每个 $1 \leq i \leq D$ 的整数 $i$，有 $p_i$ 道分值为 $100i$ 的题目。这 $p_1 + \dots + p_D$ 道题目就是 AtCode 上收录的全部题目。

AtCode 的用户拥有一个被称为“综合得分”的数值。用户的综合得分由以下两部分组成：

• 基础得分：用户所解所有题目的分数之和。
• 完成奖励：如果用户解完了所有分值为 $100i$ 的 $p_i$ 道题目，则除了基础得分外，还能获得 $c_i$ 分的完成奖励（$1 \leq i \leq D$）。

刚成为 AtCode 新用户的高桥君还没有解过任何题目。他的目标是让综合得分达到 $G$ 分或以上。为此，他至少需要解多少道题目？

输入格式

输入以如下格式从标准输入读入。

$D$ $G$
$p_1$ $c_1$
$p_2$ $c_2$
$\vdots$
$p_D$ $c_D$

输出格式

输出为达到综合得分 $G$ 分所需解答的最小题目数。保证一定可以达到目标分数（见约束条件）。

样例 1

输入

2 700
3 500
5 800

输出

3

样例 2

输入

2 2000
3 500
5 800

输出

7

样例 3

输入

2 400
3 500
5 800

输出

2

样例 4

输入

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

输出

66

说明/提示

约束条件

• $1 \leq D \leq 10$
• $1 \leq p_i \leq 100$
• $100 \leq c_i \leq 10^6$
• $100 \leq G$
• 输入中的所有数值均为整数。
• $c_i, G$ 均为 $100$ 的倍数。
• 一定存在解，使得综合得分可以达到 $G$ 分。

样例解释 1

在本例中，AtCode 有 $3$ 道 $100$ 分的题目和 $5$ 道 $200$ 分的题目。解完所有 $100$ 分题目可获得 $500$ 分的完成奖励，解完所有 $200$ 分题目可获得 $800$ 分的完成奖励。高桥君的目标是让综合得分达到 $700$ 分或以上。实现目标的一种方法是解 $4$ 道 $200$ 分题目，获得 $800$ 分基础得分。但如果解完全部 $3$ 道 $100$ 分题目，则基础得分为 $300$ 分，加上 $500$ 分的完成奖励，总分为 $800$ 分，可以用更少的题目数达成目标。

样例解释 2

与样例 1 类似，但这次高桥君的目标是 $2000$ 分。在这种情况下，必须解完所有 $5$ 道 $200$ 分题目，并且还需再解 $2$ 道 $100$ 分题目，综合得分才能达到 $2000$ 分。

样例解释 3

再次与样例 1 类似，但这次目标为 $400$ 分。只需解 $2$ 道 $200$ 分题目即可达成目标。

样例解释 4

只有 $1$ 道 $500$ 分的题目，即使只有一道题，也可以通过解完它获得完成奖励。

由 ChatGPT 4.1 翻译