E. Панорама города
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса в Нью-Йорке! Она хочет сделать несколько снимков знаменитых небоскребов и отправить набор фотографий Бобу. Алиса хочет составить наиболее красивый набор фотографий, и в этом ей требуется ваша помощь.

В городе $$$n$$$ зданий, расположенных в линию слева направо, $$$i$$$-е из них имеет положительную высоту $$$h_i$$$. Высоты всех $$$n$$$ зданий в городе различны. Кроме того, у каждого здания есть параметр красоты $$$b_i$$$. Красота зданий может быть положительна или отрицательна (или равна нулю), потому что некоторые здания портят вид.

Набор фотографий состоит из одной или более фотографий зданий. На каждом фото должно быть изображено одно или несколько зданий, расположенных подряд. Каждое здание должно попасть на ровно одно фото. Другими словами, если есть здание, которое не попало ни на одно фото, или присутствует более чем на одном фото, то такой набор фотографий считается некорректным.

Красота одной фотографии равняется красоте $$$b_i$$$ самого низкого здания на фотографии. Общая красота набора фотографий равна сумме красот всех фотографий в наборе. Помогите Алисе определить максимально возможную красоту корректного набора фотографий.

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — количество зданий.

Вторая строка содержит $$$n$$$ различных целых чисел $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le n$$$), где $$$i$$$-е число равно высоте $$$i$$$-го здания.

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$-10^9 \le b_i \le 10^9$$$), где $$$i$$$-е число равно красоте $$$i$$$-го здания.

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

Выведите одно число — максимальную красоту, которую может иметь корректный набор фотографий.

Примеры
Входные данные
5
1 2 3 5 4
1 5 3 2 4
Выходные данные
15
Входные данные
5
1 4 3 2 5
-3 4 -10 2 7
Выходные данные
10
Входные данные
2
2 1
-2 -3
Выходные данные
-3
Входные данные
10
4 7 3 2 5 1 9 10 6 8
-4 40 -46 -8 -16 4 -10 41 12 3
Выходные данные
96
Примечание

В первом примере максимальная красота достигается, если Алиса сделает пять фотографий, каждая из которых содержит одно здание.

Во втором примере Алиса может достичь максимальной красоты набора, равной $$$10$$$, если сделает четыре фотографии: три содержат одно здание каждая (здания $$$1$$$, $$$2$$$ и $$$5$$$), их красоты равны $$$-3$$$, $$$4$$$ и $$$7$$$ соответственно, и еще одна фотография содержит здания $$$3$$$ и $$$4$$$, ее красота равна $$$2$$$.

В третьем примере Алиса может просто сделать одно фото всего города.

В четвертом примере Алиса может сделать следующие фотографии для достижения максимальной красоты набора: отдельно фотографии зданий $$$1$$$, $$$2$$$, $$$8$$$, $$$9$$$ и $$$10$$$, а также одно фото зданий $$$3$$$, $$$4$$$, $$$5$$$, $$$6$$$ и $$$7$$$ вместе.