BOJ 7281 Internetas

문제 링크:

문제 내용

당신은 인터넷 연결이 좋지 못한 환경에 있습니다. $N$개의 시점 $T_i$와 그 시각에 인터넷이 연결되었는지 여부 $M_i$가 주어질 때, $T_1$과 $T_N$ 사이에 인터넷이 끊겨 있었을 수 있는 가장 긴 시간을 구하세요.

입력

첫 줄에는 $N$이 주어집니다. ($2 \le N \le 1000$)

다음 $N$줄에는 각각 인터넷 연결을 확인한 시점 $T_i$와 그때 인터넷이 연결되었는지 여부를 나타내는 정수 $M_i$가 주어집니다. $M_i$는 인터넷이 연결되었으면 1, 아니면 0이며, $M_1 = M_N = 1$입니다. ($1 \le T_i \le 1\;000\;000$, $T_i < T_{i+1}$)

출력

문제의 정답을 출력합니다.

문제 풀이