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