Хмарочоси#254

Хмарочоси

1 секунда

256 мегабайтів

Середня

Козак Вус живе у хмарочосі.

Оскільки він почав працювати будівельником, то $n$ замовників дали йому завдання побудувати $n$ хмарочосів. Один з них має знаходитися на відстані одного кілометра від хмарочоса Козака Вуса, інший має бути на відстані двох кілометрів, інший має бути на відстані трьох кілометрів і так далі. Всі хмарочоси (у тому числі й Козака Вуса) мають знаходитися на одній прямій, причому хмарочос Вуса має бути найлівішим з усіх.

$i$ -ий замовник хоче, щоб його хмарочос мав висоту $a_{i}$ a_i поверхів. Проте замовникам все одно, на якій відстані їхні хмарочоси будуть знаходитися від хмарочоса Вуса. Тому Козак може сам вирішувати, у якому порядку від свого хмарочоса будувати інші хмарочоси.

Козак Вус хоче зробити так, щоб вигляд з його хмарочоса був якнайгарнішим. Будемо вважати, що $i$ -ий поверх певного хмарочоса видний з хмарочоса Вуса лише якщо між ними немає іншого хмарочоса, який матиме $i$ -ий поверх. Козак вважає, що кожен поверх $i$ -го хмарочоса має красу $b_{i}$ b_i. Тому він хоче, щоб сумарна краса всіх поверхів, які він бачитиме зі свого хмарочоса, була максимально можливою.

Приклад для $n$ = 4.

На малюнку зображено приклад для $n = 4$ n=4. На відстані одного кілометра побудували двоповерховий хмарочос з красою $4$ . Далі одноповерховий з красою $2$ . Далі триповерховий з красою $1$ . Нарешті останнім побудували хмарочос висотою $4$ поверхи та красою $3$ . З хмарочоса Вуса видно лише обидва поверхи першого хмарочоса, третій поверх третього та четвертий поверх четвертого хмарочосів. Відповідно рахуємо сумарну красу цих поверхів: $4 + 4 + 1 + 3 = 12$ 4+4+1+3=12. Зверніть увагу, що це може бути не оптимальним порядком побудови.

Допоможіть йому знайти максимально можливу красу.

Вхідні дані

Перший рядок містить одне ціле число $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \leq n \leq 10^5) — кількість хмарочосів, які потрібно побудувати.

Другий рядок містить $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \dots, a_n ( $1 \leq a_{i} \leq 1 0^{9}$ 1 \leq a_i \leq 10^9) — висоти хмарочосів.

Третій рядок містить $n$ цілих чисел $b_{1}, b_{2}, \dots, b_{n}$ b_1, b_2, \dots, b_n ( $1 \leq b_{i} \leq 1 0^{9}$ 1 \leq b_i \leq 10^9) — красоти поверхів у хмарочосах.

Вихідні дані

Виведіть одне ціле число — максимально можливу сумарну красу.

Приклади

Приклад

Приклад 1

Оцінювання

( $10$ балів) $1 \leq n \leq 10, 1 \leq a_{i} \leq 10, 1 \leq b_{i} \leq 10$ 1 \leq n \leq 10, 1 \leq a_i \leq 10, 1 \leq b_i \leq 10;
( $27$ балів) $1 \leq n \leq 1 0^{3}, 1 \leq a_{i} \leq 1 0^{3}, 1 \leq b_{i} \leq 1 0^{3}$ 1 \leq n \leq 10^3, 1 \leq a_i \leq 10^3, 1 \leq b_i \leq 10^3;
( $25$ балів) $1 \leq n \leq 1 0^{3}, 1 \leq a_{i} \leq 1 0^{9}, 1 \leq b_{i} \leq 1 0^{9}$ 1 \leq n \leq 10^3, 1 \leq a_i \leq 10^9, 1 \leq b_i \leq 10^9;
( $38$ балів) без додаткових обмежень.