G. Квест
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Возвращаясь домой, солдат встретил колдунью, которая предложила ему пройти увлекательный квест. Солдату стало интересно, и он попросил колдунью объяснить ему правила.

Теперь перед собой солдат видит $$$n$$$ холмов, расположенных в ряд слева направо, причем $$$i$$$-й холм имеет высоту $$$a_i$$$. Солдат может прыгнуть с одного холма на любой другой правее данного, если высота холма, с которого прыгает солдат, строго меньше, чем высота холма, на который он прыгает. Когда солдат оказывается на $$$i$$$-м холме, он получает $$$b_i$$$ монет (если $$$b_i \lt 0$$$, солдат отдает $$$|b_i|$$$ монет). Солдат может начать и закончить на любом холме. Также солдат имеет право отказаться от квеста и уйти с нулевым выигрышем.

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

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

В первой строке вводится одно натуральное число $$$n$$$ ($$$1 \le n \le 3\,000$$$).

Во второй строке перечислены $$$n$$$ целых чисел $$$a_i$$$ ($$$0 \le a_i \le 10^{9}$$$).

В третьей строке перечислены $$$n$$$ целых чисел $$$b_i$$$ ($$$-10^{9} \le b_i \le 10^{9}$$$).

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

В единственной строке выведите одно число — максимальное количество монет, которые сможет получить солдат после прохождения квеста.

Примеры
Входные данные
3
1 2 3
-1 2 2
Выходные данные
4
Входные данные
4
2 3 1 4
1 1 5 -1
Выходные данные
5
Входные данные
5
0 4 0 2 0
8 7 1 -12 2
Выходные данные
15