| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 23 | 15 | 15 | 65.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.
3 1 2 2 2 3 0 1 5
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.
3 1 2 2 2 3 1 2 1
0
The steaks ready in his steak house can fulfill all orders without any further cooking.
3 1 2 2 2 3 5 0 0
-1
It is impossible to have $5$ steaks of doneness level $1$.
ICPC > Regionals > Asia Pacific > Indonesia > Indonesia National Contest > INC 2022 B번
ICPC > Regionals > Asia Pacific > Indonesia > Indonesia National Contest > INC 2023 연습 세션 PB번