페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#7022
서브태스크

반품 회수 2초 1024MB

문제

아래 그림과 같이 직선 형태의 도로상에 왼쪽부터 오른쪽으로 1번부터 N번까지 번호가 붙어 있는 N개의 집이 있다.

i (1 \le i \le N)번 집의 위치는 X_i (X_i \gt 0)이다.

택배 회사는 한 대의 트럭을 이용해 N개의 집을 방문하면서 반품되는 물건을 회수하려고 한다.

트럭은 택배 회사가 있는 위치 0에서 시각 0에 출발하고, i번 집은 시각 T_i에 반품할 물건을 내놓는다.

트럭은 1의 속력으로 이동하므로, d만큼의 거리를 이동하는데 d시간이 걸린다.

또한, 트럭은 필요하면 움직이지 않고 제자리에 멈춰서 기다릴 수 있다.

트럭은 반품할 물건이 나와있는 집의 위치를 지나면 순식간에 물건을 회수할 수 있다.

즉, 물건을 회수하는 데 소요되는 시간은 0이다.

따라서 트럭은 위치 X_i를 시각 T_i 또는 그 이후에 지나면 i번 집에서 내놓은 물건을 회수할 수 있다.

직선 형태의 도로 위에 있는 집의 위치와 반품할 물건을 내놓는 시각이 주어질 때,
트럭이 모든 물건을 회수해서 다시 택배 회사로 돌아오는 데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하라.

[제약 조건]

  • 1 \le N \le 3\,000

  • 1 \le X_1 \lt X_2 \lt \cdots \lt X_N \le 10^8

  • 0 \le T_i \le 10^8 (1 \le i \le N)


입력

첫 번째 줄에 반품할 물건을 내놓을 집의 개수 N이 주어진다.

두 번째 줄에 각 집의 위치 X_1, X_2, \cdots, X_N이 공백으로 구분되어 주어진다.

세 번째 줄에 각 집이 물건을 내놓는 시각 T_1, T_2, \cdots, T_N이 공백으로 구분되어 주어진다.


출력

첫 번째 줄에 트럭이 모든 물건을 회수하고 다시 택배 회사로 돌아오기 위해 필요한 시간의 최솟값을 출력한다.


부분문제

번호 점수 조건
#110점

N=2

#215점

N \le 9

#35점

모든 1 \le i \le N에 대해 T_i = 0

#425점

모든 2 \le i \le N에 대해 T_{i-1} \le T_i

#545점

추가 제약 조건 없음


예제1

입력
4
25710
2041611
출력
23

예제2

입력
3
123
321
출력
6

태그

출처

KOI 1차 2024 초3/고1

역링크