인터넷

면접 대비

시간 제한1초메모리 제한1024 MB

요약

연결 상태를 기록한 측정값들이 주어지고 처음과 마지막은 연결 상태일 때, 인터넷이 끊겨 있었을 수 있는 가장 긴 시간을 구한다.

문제

토마스의 인터넷 연결은 자주 불안정해서 가끔씩 연결이 끊긴다. 토마스는 끊긴 인터넷이 다시 연결될 때까지 얼마나 오래 기다려야 할 수 있는지 알고 싶어서, 이따금씩 그 순간에 인터넷 연결이 있는지 확인하고 기록해 둔다.

토마스는 첫 번째 측정과 마지막 측정에서는 인터넷 연결이 있었다는 것을 기억한다.

토마스가 인터넷 없이 지냈을 수 있는 가장 긴 시간을 구해서 그를 도와주자.

첫째 줄에 정수 $N$ 이 주어진다. $N$ 은 토마스가 수행한 측정의 횟수이다.

이어지는 $N$ 개의 줄 각각에는 정수 두 개 $T_i$ 와 $M_i$ 가 주어진다. $T_i$ 는 토마스가 $i$ 번째 측정을 한 시각이고, $M_i$ 는 그 측정의 결과이다. 측정한 순간에 인터넷 연결이 있었으면 $M_i$ 는 $1$ , 없었으면 $0$ 이다.

측정은 $T_i$ 가 증가하는 순서로 주어진다.

토마스가 인터넷 없이 지냈을 수 있는 가장 긴 시간 간격을 정수 하나로 출력한다.