В ЛКШ наконец-то появилось поле для игры в баскетбол, и на радостях Демид решил провести баскетбольную зарядку. На зарядку к Демиду пришло \(2 \cdot n\) человек, и он построил их в два ряда по \(n\) человек в каждом. В каждом из рядов он пронумеровал игроков от \(1\) до \(n\) слева направо.
Теперь Демид хочет выбрать команду для игры в баскетбол. Он будет выбирать игроков слева направо, и номер каждого следующего взятого игрока будет строго больше, чем предыдущего взятого. А для того, чтобы не отдавать предпочтения одному из рядов, каждый следующий выбранный школьник должен стоять не в том же ряду, что предыдущий. Первый выбранный школьник может быть любым из всех \(2n\), а количество игроков в команде не ограничено.
Демид считает, что команда тем лучше, чем больше суммарный рост ее игроков. Помогите Демиду определить максимальный суммарный рост игроков команды, которую он может выбрать.
Выходные данные
Выведите одно число — максимальное суммарный рост игроков в команде, которую может выбрать Демид.
Примечание
В первом примере Демид может выбрать такую команду:
Во втором примере Демид может выбрать такую команду:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
9 3 5 7 3
5 8 1 4 5
|
29
|
|
2
|
3
1 2 9
10 1 1
|
19
|
|
3
|
1
7
4
|
7
|