15714번 - 열려라 참깨

디디와 chogahui05는 우연히 주운 보물지도를 따라 목적지에 도착했다. 그런데 그 보물들은 퍼즐을 풀어야만 열리는 금고에 보관되어 있었다. 퍼즐의 내용은 다음과 같다.

가로 N, 세로 2³¹ 크기의 격자로 이루어진 판이 있다.

N개의 세로줄에는, 매 줄마다 자갈과 그 자갈을 위치시켜야 하는 홈이 각각 하나씩 있다.

1초에 한번씩 연속된 세로줄에 있는 자갈 X개를 선택하여, 전부 위로 1칸 올리거나, 아래로 1칸 내릴 수 있다. 또한 홈에 위치한 자갈도 움직일 수 있다. 모든 자갈을 홈 안에 넣으면 퍼즐이 풀리며 금고의 문이 열리게 된다.

편의상 자갈과 홈의 크기는 1×1이며, 자갈이 홈의 딱 정중앙에 위치해야 한다. 또한 자갈이 격자판을 벗어나게 해선 안 된다.

디디는 chogahui05가 자리를 비운 사이 퍼즐을 최대한 빨리 풀어 보물을 가지고 도망치려고 한다. 디디가 이 퍼즐을 풀 수 있는 가장 빠른 시간(초)을 구하는 프로그램을 작성해야 한다.

위는 가로3 세로5 격자판의 예시이다. (●는 자갈, ✕는 홈)

가장 최적의 정답 중 하나는 세로줄 기준으로 1~3번째 줄에 있는 돌을 전부 한 칸 올리고, 2번째 줄에 있는 돌을 연속으로 두 칸 내리는 것이다. 위 경우 3초가 소요된다.

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000)

둘째 줄에 자갈의 위치(i, Y_i)를 나타내는 정수 Y_i가 공백으로 구분되어 주어진다. (i = 1, 2, ..., N, 0 ≤ Y_i < 2³¹)

셋째 줄에 홈의 위치(i, Y_i)를 나타내는 정수 Y_i가 공백으로 구분되어 주어진다. (i = 1, 2, ..., N, 0 ≤ Y_i < 2³¹)

문제의 정답을 출력하라.