Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 8 点
問題文
日本で現在使われている硬貨には 1 円玉、5 円玉、10 円玉、50 円玉、100 円玉、500 円玉の 6 種類あります。
これらのうち、穴が開いているものは 5 円玉と 50 円玉の 2 種類です。
高橋君は日本のとある場所で店を経営しており、ある日、彼の店には N 人の客が訪れました。i \, (1 \leq i \leq N) 番目に訪れた客は A_i 円の品物に対して B_i 円を支払い、高橋くんはそれぞれの客に対し硬貨の総数が最小になるようにお釣りを出しました。
その日にお釣りとして用いられた硬貨のうち、穴が開いているものは何枚か求めてください。
ただし、高橋くんは 6 種類の硬貨をそれぞれ十分な枚数持っているとします。
制約
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq B_i \leq 10^3
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 \vdots A_N B_N
出力
答えを出力せよ。
入力例 1
2 40 100 105 120
出力例 1
2
1 人目の客には 60 円のお釣りを出すので、硬貨の総数が最小となるように 10 円玉 1 枚と 50 円玉 1 枚を用います。
2 人目の客には 15 円のお釣りを出すので、硬貨の総数が最小となるように 5 円玉 1 枚と 10 円玉 1 枚を用います。
これらのうち穴が開いている硬貨は 2 枚です。
入力例 2
6 1 2 1 6 1 11 1 51 1 101 1 501
出力例 2
2
Score : 8 points
Problem Statement
There are six kinds of coins used in Japan now: 1-yen, 5-yen, 10-yen, 50-yen, 100-yen, and 500-yen coins. Two of them, 5-yen and 50-yen coins, have holes in them.
Takahashi runs a shop somewhere in Japan. One day, N customers visited his shop. The i-th customer paid B_i yen for a product worth A_i yen, and Takahashi gave each customer the change using the minimum number of coins.
Among the coins used as the changes on that day, how many had holes in them?
Here, assume that Takahashi had enough of each kind of coin.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq B_i \leq 10^3
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 B_1 \vdots A_N B_N
Output
Print the answer.
Sample Input 1
2 40 100 105 120
Sample Output 1
2
To the 1-st customer, he gives 60 yen as the change, using one 10-yen coin and one 50-yen coin to minimize the number of coins.
To the 2-nd customer, he gives 15 yen as the change, using one 5-yen coin and one 10-yen coin to minimize the number of coins.
Among these coins, 2 of them have holes in them.
Sample Input 2
6 1 2 1 6 1 11 1 51 1 101 1 501
Sample Output 2
2