반품 회수

문제

직선 도로 위의 위치 0에 트럭이 있다. N개의 집이 위치 X1 < X2 < ... < XN에 있으며, 집 i의 물건은 Ti 시각 이후부터 수거할 수 있다.

트럭은 속도 1로 이동하며, 멈춰서 기다릴 수 있다. 모든 물건을 수거하고 위치 0으로 돌아오는 최소 시간을 구하시오.

제한

• 1 ≤ N ≤ 3,000
• 1 ≤ Xi ≤ 10^8
• 0 ≤ Ti ≤ 10^8
• 시간 제한: 1초

입출력 예시

입력 1

4
2 20
5 4
7 16
10 11

출력 1

23

입력 2

3
1 3
2 2
3 1

출력 2

6