P15590 [ICPC 2020 Jakarta R] Comic Binge

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 $A_i$ hours for Andi to finish reading the $i^{th}$ book, while Budi needs $B_i$ 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: - Budi, being the older brother, may skip one book after reading a book. More precisely, after Budi has finished reading the $i^{th}$ book, he may start reading the $(i+2)^{th}$ book without reading the $(i+1)^{th}$ book at all. - If Budi does not skip the $i^{th}$ book, Andi, being the younger brother, is not allowed to start reading the $i^{th}$ book before Budi finished reading it. If Budi skips the $i^{th}$ book, there is no special condition for the book. Both Andi and Budi must read the $1^{st}$ book and $N^{th}$ 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 $N^{th}$ 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 \leq N \leq 1000$) representing the number of comic books. The second line contains $N$ integers: $A_i$ ($1 \leq A_i \leq 1000$) representing the time in hours needed for Andi to read each book. The third line contains $N$ integers: $B_i$ ($1 \leq B_i \leq 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.

#### Explanation for the sample input/output #1 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 | | #### Explanation for the sample input/output #2 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 | |