← 返回题目列表

AtCoder · past202104_k

K. 普通优惠券

中文机器翻译题面 查看原题

分数: 6 点

警告

2021 年 4 月 24 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

一家便利店 伦伦玛特 目前出售 N 产品。 的 i-第产品的价格为 P_i 日元和效用 Q_i 点。 另外,本店还举办以下活动:

  • 对于每个 100 花费日元,价值一张礼券 奖励 20 日元。 (小于 100 日元被丢弃。)

你有 10^{100} 日元。现在,您将选择一些(可能没有)已出售的产品并购买它们。您不能多次购买同一产品。
让我们定义购买分数 S as S = T - Q + R,其中 Q 是您购买的产品的总价, T 是您购买的产品的总效用,并且 R 是您收到的优惠券的总价值。
找到最大可能值 S.

约束

  • 输入中的所有值都是整数。
  • 1 \le N \le 10^5
  • 1 \le P_i,U_i \le 10^4 (1 \le i \le N)

输入

输入由标准输入按以下格式给出:

N
P_1 U_1
P_2 U_2
\vdots
P_N U_N

输出

打印答案。


示例输入 1

3
50 40
30 29
60 55

示例输出 1

5

例如,如果您购买 1-st 和 3-rd产品,总价为 110 日元,总效用为 95 积分,您收到的优惠券总价值为 20 日元,分数为 95 - 110 + 20 = 5.
不可能获得更高的分数。


示例输入 2

1
652 175

示例输出 2

0

最好不购买任何产品。


示例输入 3

10
859 346
669 705
344 425
693 747
24 808
462 344
930 67
878 35
906 253
531 832

示例输出 3

1696