스테이크 굽기

시간 제한1초메모리 제한2048 MB

요약

각 익힘 단계의 스테이크 수와 인접 단계 사이의 조리 시간이 주어질 때, 모든 주문을 맞추는 최소 총 시간을 구하고 불가능하면 -1을 출력합니다.

난이도: 보통10점 중 5점
유형: 그리디, 구현, 배열
정답자: 아직 제출이 없습니다

문제

Morgan은 스테이크 하우스의 요리사이다. 이 가게에서 스테이크의 익힘 정도는 $1$ 부터 $N$ 까지 $N$ 단계로 나뉜다. 현재 Morgan은 익힘 정도가 $i$ 인 스테이크를 $A_i$ 개 준비해 두었다.

익힘 정도가 $i$ 인 주문이 $B_i$ 개 있으며, 모두 처리해야 한다. Morgan은 주문된 익힘 정도에 맞게 스테이크를 요리할 수 있다. $1 \le i < N$ 인 각 $i$ 에 대해, 익힘 정도 $i$ 인 스테이크를 $i + 1$ 로 익히는 데 $T_i$ 초가 걸린다. Morgan은 한 번에 스테이크 한 개만 요리할 수 있다.

모든 주문을 처리하는 데 걸리는 최소 총 시간을 구하라. 주문을 처리할 수 없으면 그 사실을 판단하라.

출력

모든 주문을 처리할 수 있으면 최소 총 시간을 정수로 한 줄에 출력한다. 그렇지 않으면 -1을 한 줄에 출력한다.

입력

첫 줄에 정수 $N$ ( $2 \le N \le 100000$ )이 주어진다. 둘째 줄에는 $N - 1$ 개의 정수 $T_i$ ( $1 \le T_i \le 1000$ )가 주어진다. 이는 익힘 정도 $i$ 인 스테이크를 $i + 1$ 로 익히는 데 걸리는 시간이다. 셋째 줄에는 $N$ 개의 정수 $A_i$ ( $0 \le A_i \le 1000$ )가 주어진다. 이는 익힘 정도 $i$ 인 스테이크의 개수이다. 넷째 줄에는 $N$ 개의 정수 $B_i$ ( $0 \le B_i \le 1000$ )가 주어진다. 이는 익힘 정도 $i$ 인 주문의 개수이다.

예제3

예제 1
입력
```
3
1 2
2 2 3
0 1 5
```
예상 출력
```
5
```
예제 2
입력
```
3
1 2
2 2 3
1 2 1
```
예상 출력
```
0
```
예제 3
입력
```
3
1 2
2 2 3
5 0 0
```
예상 출력
```
-1
```