엘리베이터

아주 중요한 일을 맡았다. 새로 지은 고층 빌딩의 엘리베이터를 책임지게 된 것이다.

$n$명의 사람이 $0$층에 있는 지하 주차장에 와서 위층으로 올려다 줄 엘리베이터를 기다린다. 정확히 말해 $i$번째 사람은 $t_i$ 시각에 엘리베이터에 오고 $a_i$층으로 가려 한다. 엘리베이터의 정원은 무한이다. 즉 어느 순간에든 엘리베이터를 이용하는 사람 수에는 제한이 없다. 모든 $t_i$는 서로 다르다. 승객은 엘리베이터가 $0$층에 있는 동안 항상 탄다.

엘리베이터는 다음 알고리즘을 따른다. 승객을 태워 보내라는 명령을 내릴 때까지 $0$층에서 문을 열고 기다리다가, 가야 할 가장 높은 층(현재 엘리베이터에 탄 모든 승객의 $a_i$ 중 최댓값)으로 이동하면서 승객을 내려 주고, 다시 주차장으로 돌아온다. 엘리베이터는 다음 층으로(또는 이전 층으로) 이동하는 데 $1$만큼의 시간이 걸린다. 문을 여닫는 시간과 승객이 타고 내리는 시간은 무시할 수 있다. $0$ 시각에 엘리베이터는 $0$층에 있다.

모두를 내려 준 뒤 엘리베이터가 $0$층으로 돌아오는 시각을 최소로 만들고 싶다.

입력에는 하나 이상의 테스트 케이스가 들어 있다.

각 테스트 케이스의 첫 줄에는 정수 $n$이 주어진다. $n$은 승객 수이다 ($1 \le n \le 2 \cdot 10^5$).

다음 $n$개 줄에는 각각 공백으로 구분된 두 정수 $t_i$와 $a_i$가 주어진다. $t_i$는 $i$번째 승객이 엘리베이터에 오는 시각이고 $a_i$는 $i$번째 승객의 목적지 층이다 ($1 \le t_i, a_i \le 10^9$).

한 테스트 케이스의 모든 $t_i$는 서로 다르고, 승객은 $t_i$가 커지는 순서로 입력에 나타난다.

모든 테스트 케이스의 $n$ 값의 합은 $2 \cdot 10^5$을 넘지 않는다. 테스트 케이스는 별도의 구분자 없이 연달아 주어진다.

각 테스트 케이스마다 모든 승객을 내려 준 뒤 엘리베이터가 돌아오는 시각의 최솟값을 정수 하나로 출력한다.