Условие

На городской ярмарке установлены две линии торговых стоек: верхняя и нижняя. В каждой линии ровно n стоек, пронумерованных слева направо от 1 до n.

Для каждой стойки известна её прибыль, если открыть её на время фестиваля. Прибыль верхних стоек задана массивом a, а нижних — массивом b.

Организаторы хотят открыть несколько стоек так, чтобы маршрут охраны оставался удобным. Поэтому выбранные стойки должны удовлетворять такому правилу:

• если открыть две стойки с соседними номерами, то они обязательно должны находиться в разных линиях.

Иными словами, нельзя открыть две соседние по номеру стойки в одной и той же линии.

Требуется найти максимальную суммарную прибыль, которую можно получить.

Входные данные

В первой строке записано одно целое число n — количество стоек в каждой линии (1 <= n <= 100000).

Во второй строке записаны n целых чисел a1, a2, ..., an — прибыли верхних стоек (1 <= ai <= 10^9).

В третьей строке записаны n целых чисел b1, b2, ..., bn — прибыли нижних стоек (1 <= bi <= 10^9).

Выходные данные

Выведите одно целое число — максимальную суммарную прибыль.

Примечание

Можно открывать любое количество стоек, в том числе одну или ни одной, если это оптимально.

Примеры

Пример 1

Входные данные

5
9 3 5 7 3
5 8 1 4 5

Выходные данные

29

Пример 2

Входные данные

3
1 100 3
50 2 50

Выходные данные

200

Пример 3

Входные данные

1
7
11

Выходные данные

11

Пояснение к первому примеру

Можно открыть стойки с прибылями 9 (верхняя, 1), 8 (нижняя, 2), 7 (верхняя, 4) и 5 (нижняя, 5). Их суммарная прибыль равна 29.