에스컬레이터

새로운 종류의 에스컬레이터를 발명했다. 바로 양방향 에스컬레이터다. 일반 에스컬레이터는 사람을 한쪽 끝에서 다른 쪽 끝으로만 데려가지만, 양방향 에스컬레이터는 양쪽 끝 중 어느 쪽에서든 다른 쪽 끝으로 사람을 데려갈 수 있다.

양방향 에스컬레이터가 한쪽 끝에서 다른 쪽 끝까지 사람을 데려가는 데는 10초가 걸린다. 즉, 어떤 사람이 시각 T에 양방향 에스컬레이터의 한쪽 끝에서 탑승하면 시각 T + 10에 반대쪽 끝에서 내린다. 이 사람은 시각 T + 10에는 더 이상 양방향 에스컬레이터를 이용하지 않는다.

양방향 에스컬레이터를 아무도 이용하지 않으면 즉시 멈춘다. 따라서 처음에는 멈춰 있는 상태다.

양방향 에스컬레이터가 멈춰 있을 때 어떤 사람이 한쪽 끝에서 탑승하면, 에스컬레이터는 자동으로 켜지고 그 사람이 가려는 방향으로 움직인다.

어떤 사람이 양방향 에스컬레이터에 도착했을 때 에스컬레이터가 이미 그 사람이 가려는 방향으로 움직이고 있으면, 그 사람은 즉시 탑승한다. 반대로 가려는 방향의 반대 방향으로 움직이고 있으면, 에스컬레이터가 멈출 때까지 기다렸다가 그제야 탑승한다. 에스컬레이터는 매우 커서 여러 사람이 동시에 탑승할 수 있다.

양방향 에스컬레이터에는 아마도 양자역학적 효과(아니면 그냥 우연)와 관련된 매우 이상한 성질이 하나 있다. 에스컬레이터가 멈추는 바로 그 순간에 도착하는 사람은 아무도 없다.

이제 양방향 에스컬레이터의 동작을 알았으니, 이를 시뮬레이션하는 작업을 맡게 된다. N명의 사람에 대한 정보, 즉 에스컬레이터에 도착하는 시각과 가려는 방향이 주어질 때, 에스컬레이터가 마지막으로 멈추는 시각을 구해야 한다.

첫째 줄에는 양방향 에스컬레이터를 이용할 사람의 수를 나타내는 정수 N (1 ≤ N ≤ 10^4)이 주어진다.

다음 N개의 줄에는 각각 두 정수 t_i와 d_i (1 ≤ t_i ≤ 10^5, 0 ≤ d_i ≤ 1)가 주어진다. t_i는 i번째 사람이 에스컬레이터에 도착하는 시각이고, d_i는 그 사람이 가려는 방향이다. d_i가 0이면 왼쪽 끝에서 오른쪽 끝으로 가려는 것이고, d_i가 1이면 오른쪽 끝에서 왼쪽 끝으로 가려는 것이다. 모든 t_i 값은 서로 다르며 오름차순으로 주어진다.

마지막 사람이 양방향 에스컬레이터에서 내리는 시각을 한 줄에 출력한다.