폴더

면접 대비

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

요약

각 폴더 목록을 한 번 뒤집는 버튼을 쓸 수 있을 때, 목표 파일을 열기까지 커서를 최소 몇 초 움직여야 하는지 구합니다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 구현
정답자: 아직 제출이 없습니다

문제

주쿨은 슈퍼컴퓨터를 가지고 있다. 이 컴퓨터에서는 커서만 느리게 움직인다. 주쿨은 특정 파일을 열고 싶다. 그는 자기 컴퓨터에 있는 모든 폴더의 내용을 정확히 알고 있지만 명령줄은 쓸 줄 몰라서, 폴더를 하나씩 클릭하며 파일 트리를 따라간다.

탐색기 창에서는 폴더 안의 하위 폴더와 파일이 위아래로 목록을 이룬다. 주쿨이 하위 폴더를 클릭하면, 그 하위 폴더의 목록이 이전에 보이던 목록을 대신한다.

목표 파일에 도달하려면 주쿨은 $N$ 개의 폴더를 열어야 하며, 각 폴더에서 올바른 하위 폴더나 파일로 이동해야 한다. 처음에 커서는 목록의 첫 번째 항목 위에 있다. 커서를 위나 아래로 한 칸 옮기는 데 1초가 걸린다. 폴더나 파일을 여는 클릭에는 시간이 들지 않는다. 클릭하는 동안 커서는 움직이지 않는다. 따라서 주쿨이 목록의 세 번째 항목을 클릭하면, 하위 폴더가 열린 뒤에도 커서는 새 목록의 세 번째 항목에 있다.

목록의 첫 번째 항목보다 한 칸 위에는 버튼이 하나 있다. 이 버튼을 클릭하면 현재 열려 있는 목록의 항목 순서가 거꾸로 바뀐다. 이 버튼의 효과는 한 번만 적용된다. 새로 여는 폴더는 다시 원래 순서로 표시된다.

주쿨이 목표 파일을 여는 데 필요한 최소 시간을 구하라.

입력

첫 줄에는 목표 파일의 파일 트리 내 깊이인 정수 $N$ ( $1 \le N \le 10^5$ )이 주어진다. 이어서 $N$ 개의 줄이 주어지며, $i$ 번째 줄에는 정수 $M_i$ 와 $K_i$ ( $1 \le K_i \le M_i \le 10^9$ )가 주어진다. 이는 $i$ 번째 단계의 폴더에 하위 폴더와 파일이 모두 $M_i$ 개 있고, 주쿨이 그중 $K_i$ 번째에 있는 것을 열어야 한다는 뜻이다.

출력

주쿨이 목표 파일을 여는 데 걸리는 초를 나타내는 정수 하나를 출력한다.

예제2

예제 1
입력
```
2
5 3
2 1
```
예상 출력
```
4
```
예제 2
입력
```
2
5 4
2 1
```
예상 출력
```
4
```