DMOPC '18 Contest 3 P2 - Bob and French Class

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Bob has to write an essay for French class! He has already written it in English. All that's left is for him to translate it to French. Unfortunately, he is très mal at French, and needs to rely on Google Translate to write his essay.

His French teacher is well aware of this, and will know that Bob used Google Translate if any 3 consecutive words are in French.

Bob is very clever, and has stolen the marking scheme, which states that the i^{\text{th}} word is worth a_i marks if translated into French and b_i marks if left in English.

Can you write a program to maximize Bob's French mark?

Constraints

-10^3 \leq a_i, b_i \leq 10^3

Subtask 1 [10%]

There will be no more than 10 words.

Subtask 2 [90%]

There will be no more than 10^5 words.

Input Specification

The first line of input will contain a single integer N, the number of words in the essay.
The second line of input will contain N space separated integers, a_1, a_2, \ldots, a_N.
The final line of input will contain N space separated integers, b_1, b_2, \ldots, b_N.

Output Specification

A single integer, the maximal mark Bob can receive.

Sample Input 1

3
6 0 5
0 -10 0

Sample Output 1

6

Sample Input 2

4
-10 -2 -3 -4
-4 -2 -5 -1

Sample Output 2

-10

Comments

There are no comments at the moment.