시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 2048 MB23151565.217%

문제

Morgan is a chef in a steak house. In his steak house, a steak can have $N$ level of doneness, numbered from $1$ to $N$. Currently, Morgan has $A_i$ steaks of doneness level $i$ ready in his steak house.

There are $B_i$ orders of steaks with doneness level $i$ that need to be fulfilled. Morgan can cook the steaks in order to match the doneness level. For each $1 ≤ i < N$, it takes Morgan $T_i$ seconds to cook a steak from doneness level $i$ to $i + 1$. Note that Morgan can only cook one steak at a time.

Morgan asks for your help to find the minimum total time to fulfil all orders, or tell him that the orders are impossible to fulfil.

입력

Input begins with an integer $N$ ($2 ≤ N ≤ 100\, 000$). The next line contains $N - 1$ integers $T_i$ ($1 ≤ T_i ≤ 1000$) representing the time required to cook a steak of doneness level $i$ to $i+ 1$. The next line contains $N$ integers $A_i$ ($0 ≤ A_i ≤ 1000$) representing the number of steaks with doneness level $i$. The next line contains $N$ integers $B_i$ ($0 ≤ B_i ≤ 1000$) representing the number of orders for a steak with doneness level $i$.

출력

If all orders can be fulfilled, then output an integer in a single line representing the minimum total time to fulfill all orders. Otherwise, output -1 in a single line.

예제 입력 1

3
1 2
2 2 3
0 1 5

예제 출력 1

5

First, Morgan can cook both steaks with doneness level $2$ to level $3$ in $2$ seconds each. Then, Morgan can cook one steak with doneness level $1$ to level $2$ in $1$ second. Now, Morgan has $1$ steak of doneness level $1$, $1$ steak of doneness level $2$, and $5$ steaks of doneness level $3$. It is enough to fulfill all orders. There is no other way to fulfill all orders in less than $5$ seconds.

예제 입력 2

3
1 2
2 2 3
1 2 1

예제 출력 2

0

The steaks ready in his steak house can fulfill all orders without any further cooking.

예제 입력 3

3
1 2
2 2 3
5 0 0

예제 출력 3

-1

It is impossible to have $5$ steaks of doneness level $1$.