시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 72 | 24 | 22 | 40.741% |
A long vacation is coming! Andi and Budi, who are siblings, have just got a set of comic books as a gift from their uncle. As they had no plans for this vacation, they decided to stay home and read comic books.
There are N comic books, numbered from 1 to N. It takes Ai hours for Andi to finish reading the ith book, while Budi needs Bi hours to do so. Both Andi and Budi will read the comic books in ascending order of book number, one book at a time.
Because there is only one set of comic books, they decided to agree on the following rules:
Both Andi and Budi must read the 1st book and Nth book to enjoy the storyline. Also, Andi wants to read all books, while Budi might skip some books according to the above rules. Andi and Budi are considered as finished reading the comic books if and only if both Andi and Budi have finished reading the Nth book.
Your task in this problem is to determine the shortest time in hours for Andi and Budi to finish reading the comic books.
Input begins with a line containing an integer: N (1 ≤ N ≤ 1000) representing the number of comic books. The second line contains N integers: Ai (1 ≤ Ai ≤ 1000) representing the time in hours needed for Andi to read each book. The third line contains N integers: Bi (1 ≤ Bi ≤ 10) representing the time in hours needed for Budi to read each book.
Output in a line an integer representing the shortest time in hours for Andi and Budi to finish reading the comic books.
6 3 1 1 1 1 2 1 5 3 3 7 4
13
The shortest time of 13 hours can be achieved if Budi only read book 1, 3, 4, and 6. One possible reading schedule is as follows.
Hour | Andi’s reading | Budi’s reading |
---|---|---|
1 | Book 1 | |
2 | Book 1 | Book 3 |
3 | Book 1 | Book 3 |
4 | Book 1 | Book 3 |
5 | Book 2 | Book 4 |
6 | Book 3 | Book 4 |
7 | Book 4 | |
8 | Book 4 | Book 6 |
9 | Book 6 | |
10 | Book 5 | Book 6 |
11 | Book 6 | |
12 | Book 6 | |
13 | Book 6 |
2 2 1 1 1
4
Both Andi and Budi have to read book 1 and book N = 2. The shortest time for them to finish all the books is 4 hours. One possible reading schedule is as follows.
Hour | Andi’s reading | Budi’s reading |
---|---|---|
1 | Book 1 | |
2 | Book 1 | |
3 | Book 1 | Book 2 |
4 | Book 2 |