CODE FESTIVAL 2016 Relay (Parallel)

H - 早起き / Early Bird


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 100

問題文

高橋君はここ数日間の自分の生活を以下のような長さ 2N の数列として記録しました。

  • a_1, b_1, a_2, b_2, ... , a_N, b_N

これは高橋君がある時刻 T から、

  • ちょうど a_1 秒間寝続ける。
  • そのあとちょうど b_1 秒間起き続ける
  • そのあとちょうど a_2 秒間寝続ける
  • (中略)
  • そのあとちょうど a_N 秒間寝続ける
  • そのあとちょうど b_N 秒間起き続ける

というような生活を送ったことを表します。

この記録の中で高橋君は N 回起床しています。

高橋君は N 回のうち、何回早起きをしたかが気になりました。

ここで「早起き」というのは午前 4 時から午前 7 時の間に起床することを指します。 起床時間がちょうど午前 4 時や、ちょうど午前 7 時でも早起きになります。

この時間帯に起床すれば早起きになるので、 同じ日のこの時間帯に 2 回以上起床したとしても 2 回以上早起きしたことになります。

しかし高橋君は時刻 T を忘れてしまいました。

N 回の起床のうち早起きだった回数として考えられる数のうちの最大値を求めてください。

なお、 1 日は 86400 秒、午前 4 時から午前 7 時の間の時間は 10800 秒です。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq a_i, b_i \leq 10^5
  • a_i, b_i はともに整数である。

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 b_1
a_2 b_2
:
a_N b_N

出力

N 回の起床のうち早起きだった回数として考えられる数のうちの最大値を出力せよ。


入力例 1

3
28800 57600
28800 57600
57600 28800

出力例 1

2

入力例 2

10
28800 57600
4800 9600
6000 1200
600 600
300 600
5400 600
6000 5760
6760 2880
6000 12000
9000 600

出力例 2

5

Score : 100 points

Problem Statement

Takahashi recorded his daily life for the last few days as a integer sequence of length 2N, as follows:

  • a_1, b_1, a_2, b_2, ... , a_N, b_N

This means that, starting from a certain time T, he was:

  • sleeping for exactly a_1 seconds
  • then awake for exactly b_1 seconds
  • then sleeping for exactly a_2 seconds
  • :
  • then sleeping for exactly a_N seconds
  • then awake for exactly b_N seconds

In this record, he waked up N times.

Takahashi is wondering how many times he waked up early during the recorded period.

Here, he is said to wake up early if he wakes up between 4:00 AM and 7:00 AM, inclusive.

If he wakes up more than once during this period, each of these awakenings is counted as waking up early.

Unfortunately, he forgot the time T.

Find the maximum possible number of times he waked up early during the recorded period.

For your information, a day consists of 86400 seconds, and the length of the period between 4:00 AM and 7:00 AM is 10800 seconds.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq a_i, b_i \leq 10^5
  • a_i and b_i are integers.

Input

The input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
:
a_N b_N

Output

Print the maximum possible number of times he waked up early during the recorded period.


Sample Input 1

3
28800 57600
28800 57600
57600 28800

Sample Output 1

2

Sample Input 2

10
28800 57600
4800 9600
6000 1200
600 600
300 600
5400 600
6000 5760
6760 2880
6000 12000
9000 600

Sample Output 2

5

Submit提出する