자전거 주차

산네는 최근 아인트호번 기차역에서 프리미엄 자전거 주차 공간을 임대하는 사업을 구상했다. 수익을 극대화하려고 주차 자리를 $N$개의 등급(티어)으로 나누고 0부터 $N-1$까지 번호를 붙였다. 0번 등급은 프리미엄 등급으로, 승강장과 매우 가깝다. 번호가 클수록 자리의 조건이 나빠진다. 등급 $t$의 자리 수는 $x_t$개이다.

사용자는 앱을 통해 자전거를 세우고 자리를 배정받는다. 각 사용자에게는 구독 등급이 있고, 같은 등급의 자리를 기대한다. 그러나 이용 약관은 그 등급의 자리를 보장하지 않는다.

구독 등급이 $s$인 사용자가 등급 $t$의 자리를 배정받으면 다음 중 하나가 일어난다.

1. $t < s$이면 사용자가 만족하고 앱에 추천을 누른다.
2. $t = s$이면 사용자가 흡족해하며 별다른 행동을 하지 않는다.
3. $t > s$이면 사용자가 화가 나서 비추천을 누른다.

오늘 앱의 사용자는 $y_0+y_1+\ldots+y_{N-1}$명이며, $y_s$는 구독 등급이 $s$인 사용자 수이다. 사용자를 자리에 배정하는 것을 도와 달라. 각 사용자는 정확히 한 자리를 받는다. 한 자리는 한 명에게만 배정할 수 있고, 비어 있는 자리가 있어도 된다. 사용자 수는 사용 가능한 자리 수를 넘지 않는다.

산네는 앱의 평점을 최대화하고 싶어 한다. 추천 수를 $U$, 비추천 수를 $D$라 할 때 $U-D$를 최대화하라.

첫 줄에 등급 수이자 구독 등급 수인 정수 $N$이 주어진다.

둘째 줄에는 각 등급의 자리 수 $x_0, x_1, \ldots, x_{N-1}$이 $N$개의 정수로 주어진다.

셋째 줄에는 각 구독 등급의 사용자 수 $y_0, y_1, \ldots, y_{N-1}$이 $N$개의 정수로 주어진다.

사용자를 자리에 배정하는 모든 경우 중 $U-D$의 최댓값을 정수 하나로 출력한다.

• $1 \leq N \leq 3 \cdot 10^5$.
• 모든 $i = 0,1,\ldots,N-1$에 대해 $0 \leq x_i, y_i \leq 10^9$.
• $y_0+y_1+\ldots+y_{N-1} \leq x_0+x_1+\ldots+x_{N-1} \leq 10^9$.

첫 번째 예제에서는 구독 등급 0인 사용자를 0번 등급 자리에 배정한다. 구독 등급 1인 사용자 두 명은 0번 등급 자리에 배정하여 추천 2개를 얻는다. 남은 구독 등급 1인 사용자는 1번 등급 자리에 배정한다. 평점은 $2$이다.

두 번째 예제에서는 구독 등급 1인 사용자를 0번 등급 자리에, 구독 등급 2인 사용자를 1번 등급 자리에, 구독 등급 0인 사용자를 2번 등급 자리에 배정한다. 추천 2개와 비추천 1개가 나오므로 평점은 $1$이다.

세 번째 예제에서는 구독 등급 1인 사용자를 0번 등급 자리에, 구독 등급 0인 사용자를 2번 등급 자리에, 구독 등급 4인 사용자를 3번 등급 자리에 배정한다. 이 역시 추천 2개와 비추천 1개이므로 평점은 $1$이다.

네 번째 예제는 아래 그림과 같다. 구독 등급 1인 사용자를 0, 0, 3, 3번 등급 자리에 배정하면 추천 2개와 비추천 2개가 된다. 다음으로 구독 등급 2인 사용자를 1, 2, 3, 3번 등급 자리에 배정하면 추천 1개와 비추천 2개가 된다. 합계는 추천 3개와 비추천 4개이므로 평점은 $-1$이다.

다섯 번째 예제에서는 모든 사용자를 자신의 구독 등급과 같은 등급의 자리에 배정하므로 평점은 $0$이다.