Задача E. Волшебные сокровища ≡

Условие

Группа исследователей нашла необычную сокровищницу. Сокровищница представляла собой N сундуков, стоящих в линию. При этом исследователи определили ценность каждого сундука как величину a_i.

Они уже были готовы забрать все сокровища себе, но когда исcледователи осмотрелись повнимательней, то нашли на входе в сокровищницу магический артефакт, позволяющий заменить любой непрерывный отрезок сокровищ (сундуков) на такой же по длине и расположению подотрезок альтернативных сокровищ с ценностью b_i.

Требуется найти максимальную ценность сокровищ, которую можно получить, использовав этот магический артефакт (артефакт слишком старый, поэтому разрушиться после одного использования).

Формат входных данных

В первой строке дано число N (1 ≤ N ≤ 10⁵) — количество сундуков.

Во второй строке даны N чисел a_i (1 ≤ a_i ≤ 10⁹) — ценность i-го сокровища в сундуках.

Во третьей строке даны N чисел b_i (1 ≤ b_i ≤ 10⁹) — ценность i-го альтернативного сокровища.

Формат выходных данных

Требуется вывести одно число — максимальную суммарную ценность сокровищ, которую можно получить, применив артефакт.

Решения, работающие при N ≤ 100 будут набирать не более 20 баллов.

Решения, работающие при N ≤ 1000 будут набирать не более 40 баллов.

Примеры тестов

4
5 3 4 1
4 6 2 7

20

6
8 7 1 2 1 9
6 11 4 1 5 7

38