Jealousy - MarisaOJ: Marisa Online Judge

Jealousy

Time limit: 1000 ms
Memory limit: 256 MB
There are $n$ days. On $i^{th}$ day, Marisa can visit Alice Margatroid for $A_i$ happiness, or visit Patchouli Knowledge for $B_i$ happiness. But if she visits one person for 3 or more consecutive days, the other person will get jealous. What is the maximum amount of happiness she can get after $n$ days, without making anyone jealous? ### Input - The first line contains an integer $n$. - The second line contains $n$ integers $A_i$. - The third line contains $n$ integers $B_i$. ### Output - Print the maximum amount of happiness Marisa can obtain. ### Constraints - $1 \le n \le 10^5$. - $1 \le A_i, B_i \le 10^9$. ### Example Input: ``` 4 4 4 4 1 1 1 1 4 ``` Output: ``` 13 ```