K - Common Coupon Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2021/4/24 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

コンビニ「ルンルンマート」では、現在 N 個の商品が売られています。 i 個目の商品の価格は P_i 円で、効用は U_i 点です。

また、以下のルールで商品券を配布するイベントが行われています。

  • 購入金額 100 円ごとに 20 円分の商品券が 1 枚渡される。（100 円未満の端数は切り捨てる。）

10^{100} 円持っているあなたは、これらの商品から何個かを選んで ( 0 個でもよい) 購入します。ただし、同じ商品を複数回買うことはできません。
購入する商品の価格の合計を Q 円、効用の合計を T 点、渡される商品券の額面の合計を R 円として、買い物のスコア S を S = T - Q + 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 個目の商品と 3 個目の商品を買うと、価格の合計は 110 円、効用の合計は 95 点、渡される商品券の額面の合計は 20 円で、買い物のスコアは 95 - 110 + 20 = 5 となります。
スコアはこれより大きくできません。

入力例 2

1
652 175

出力例 2

0

商品を 1 つも購入しないことが最適である場合があります。

入力例 3

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

出力例 3

1696

Score : 6 points

Warning

Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

A convenient store Lun-Lun-Mart currently sells N products. The i-th product has a price of P_i yen and a utility of Q_i points. Also, the store is holding the following campaign:

  • For each 100 yen spent, one gift voucher worth 20 yen is awarded. (A fraction less than 100 yen is discarded.)

You have 10^{100} yen. Now, you will choose some (possibly none) of the products sold and buy them. You cannot buy the same product multiple times.
Let us define the score of purchase S as S = T - Q + R, where Q is the total price of products you buy, T is the total utility of products you buy, and R is the total value of vouchers you receive.
Find the maximum possible value of S.

Constraints

  • All values in input are integers.
  • 1 \le N \le 10^5
  • 1 \le P_i,U_i \le 10^4 (1 \le i \le N)

Input

Input is given from Standard Input in the following format:

N
P_1 U_1
P_2 U_2
\vdots
P_N U_N

Output

Print the answer.

Sample Input 1

3
50 40
30 29
60 55

Sample Output 1

5

For example, if you buy the 1-st and 3-rd products, the total price is 110 yen, the total utility is 95 points, and the total value of vouchers you receive is 20 yen, for the score of 95 - 110 + 20 = 5.
It is impossible to achieve a greater score.

Sample Input 2

1
652 175

Sample Output 2

0

It may be optimal to buy no products.

Sample Input 3

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

Sample Output 3

1696