分数: 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