시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 36 22 15 60.000%

문제

윤형이와 동혁이가 블록 쌓기 놀이를 한다. 두 명 모두 너비 N의 블록 건물을 쌓았는데, 윤형이는 k번째 열에 Yk개의 블록을 쌓았고 동혁이는 k번째 열에 Dk개의 블록을 쌓았다. 윤형이와 동혁이는 블록을 쌓거나 빼면서 두 개의 똑같은 건물을 만들려고 한다.

한편, 이 둘이 새로 만들려는 건물은 위 그림의 오른쪽 형태와 같이 팩맨 모양이 되어야 한다. 즉, 왼쪽에서 오른쪽으로 갈수록 블록의 개수가 감소하다가 증가하는 꼴이 되어야 한다. 또, 인접한 두 열의 블록의 개수는 정확히 한 개씩만 차이나야 하며, 블록의 개수가 가장 적은 열은 정중앙이여야 한다.

방을 어지르지 않기 위해서, 블록을 하나 뺐으면 바로 블록 상자에 넣는다. 블록을 다른 곳으로 옮겨야 한다면, 블록을 상자에 넣었다가 빼서 원하는 곳에 쌓아야 한다.

윤형이와 동혁이가 원하는 방법으로 블록 건물을 바꿀 때, 블록을 빼거나 쌓는 횟수를 최소화하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 두 블록 건물의 너비 N이 주어진다. N은 홀수이다.

두 번째 줄에는 윤형이의 블록 건물의 높이 Yk가 주어진다.

세 번째 줄에는 동혁이의 블록 건물의 높이 Dk가 주어진다.

(1 ≤ N ≤ 300,000, 0 ≤ Yk, Dk ≤ 1012)

출력

블록을 쌓거나 빼는 작업의 수의 최솟값을 출력한다.

예제 입력

3
1 2 3
3 2 2

예제 출력

3

힌트

윤형이의 블록 건물의 1번째 열에 블록 2개를 더 쌓고, 동혁이의 블록 건물의 3번째 열에 블록 1개를 더 쌓으면 된다.