問題
Pandoraスーパーにお遣いに来たKamba君がいます。Kamba君は会計をするためにレジに並びました。Kamba君は何を思ったのか、自分が何分後に会計ができるのかが気になってしまいました。
そこで、Kamba君が会計するよりも前に並んでいた全てのお客さんの「レジに到着した時刻」と、「会計にかかった時間」が与えられるのでお客さん一人当たりの平均レジ待ち時間を求めてください。ただしレジは1つしかなく、待ち行列も1列しかないとし、一人の会計が終わるまで、次の人の会計は行われないとします。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $A_1$ $B_1$ $A_2$ $B_2$ $:$ $:$ $A_N$ $B_N$
1行目にレジに並んでいるお客さんの人数 $N$ が与えられる。
2行目以降に各お客さんの情報が与えられる。具体的には $A_i$ は $i$ 番目のお客さんの到着時刻を表し、$B_i$ は $i$ 番目のお客さんの会計にかかる時間を表します。
出力
平均レジ待ち時間を一行で出力し、最後に改行を入れること。ただし、小数点以下は切り捨てること。
制約
全ての入出力ケースについて以下を満たす。
- $1 \leq N \leq 7.4 \times 10^{5}$
- $0 \leq A_i \leq 7.4 \times 10^{5}$ $(1 \leq i \leq N)$
- $1 \leq B_i \leq 7.4 \times 10^{5}$ $(1 \leq i \leq N)$
- $A_1 \leq A_2 \leq ... \leq A_N$
- $A_1 = 0$
入出力例
入力例1
3 0 3 2 2 3 1
出力例1
1
時刻 $0$ のとき、客①がレジに並びます。この際、レジに並んだと同時に会計が始まります。よって客①のレジ待ち時間は $0$ 分です。
時刻 $2$ のとき、客②がレジに並びます。この際、まだ客①が会計をしているので、待ち時間が生じます。
時刻 $3$ のとき、客①が会計を終え、客②が会計を始めます。よって、客②のレジ待ち時間は $1$ 分です。
また同時に、客③がレジに並びます。
時刻 $5$ のとき、客②が会計を終え、客③が会計を始めます。よって、客③のレジ待ち時間は $2$ 分です。
時刻 $6$ のとき、客③が会計を終えます。
よって、客①,②,③のレジ待ち時間の合計は $3$ 分で、平均待ち時間は $\frac {3}{3} = 1$ 分と分かります。
入力例2
5 0 3 0 2 0 5 0 1 0 4
出力例2
5
平均待ち時間は $\frac {29}{5} = 5.8$ になりますが、切り捨てて整数で出力をするため、 $5$ が正解になります。