VZLA2019E - Empanadas

The empanadas are a very famous dish in Venezuela. They consist of a fried dough with the shape of a half moon with delicious fillings, such as cheese, ground beef, chicken, black beans, calamari, etc. They are usually served as breakfast, but a real Venezuelan would have them no matter the time of the day.

Samuel and Sebastian are the best empanaderos, and both have their own restaurants. Everyday they sell a combo, which consists of a number of empanadas, no matter the filling. The size of the combos is not always the same for all the days.

You are visiting the country for N days, and as crazy for empanadas as you are, you will have all the empanadas you can afford during your stay. Also, you are very good friends with Samuel and Sebastian, so you will buy empanadas only from their restaurants. However, you can buy at most one combo in one day.

As a good friend, you would like to see each of their business grow, so you will alternate restaurants depending on the last place you bought a combo. For example, if the last combo you bought was from Samuel's, then the next one you buy must be from Sebastian's. Of course, you can skip buying a combo on any day if you want.

Given the number of empanadas each restaurant offers during N days, can you calculate the maximum number of empanadas you can have during your stay, without violating your own rules?

Input

The first line of the input consists of one integer N, the number of days of your stay.

The second line will have N numbers Ai separated with exactly one whitespace. The i-th number will indicate the size of the combo that Samuel's restaurant offers on the i-th day.

The third and last line will have N numbers Bi separated with exactly one whitespace. The i-th number will indicate the size of the combo that Sebastian's restaurant offers on the i-th day..

Output

Print in a single line the maximum number of empanadas you can have during your stay

Example

Input:
3
20 20 10
5 5 7 Output: 35

Constraints

1 ≤ N ≤ 103
1 ≤ Ai, Bi ≤ 20


Added by:Samuel Nacache
Date:2019-10-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Samuel Nacache - Used for Venezuelan 2019 ICPC Local Contest

hide comments
2023-11-22 01:22:00 flower
After quite some time, the solution came to me in a vision. Good problem. Here is another test case:

Input:
4
10 2 2 2
2 2 10 2

Output:
22
2020-09-02 21:40:51
O(n) dp solution
2019-11-04 18:00:12 Rocker3011
simple but cool problem.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.