F. Улучшение оружия
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп играет в игру. Игра разделена на этапы, всего $$$1337$$$ этапов. Персонаж игры использует оружие с двумя режимами атаки: физическим и элементальным. Изначально сила физической атаки оружия равна $$$1$$$, и сила элементальной атаки также равна $$$1$$$.

Во время $$$i$$$-го этапа игры происходят следующие события по очереди:

  1. Если $$$i \le n$$$, появляется монстр с физической защитой $$$a_i$$$ и элементальной защитой $$$b_i$$$. В противном случае ничего не происходит.
  2. Монокарп может выстрелить в ровно одного из живых монстров. Если физическая защита монстра не больше физической атаки персонажа или элементальная защита монстра не больше элементальной атаки персонажа, монстр будет убит. В противном случае ничего не происходит.
  3. Каждый выживший монстр наносит $$$1$$$ урона персонажу игры.

После каждого убийства Монокарп может улучшить одну из атак оружия на $$$1$$$.

Ваша задача — посчитать минимальный урон, который Монокарп может получить, чтобы убить всех монстров в игре (или сообщить, что убить всех монстров невозможно).

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 500$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 500$$$).

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 500$$$).

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

Выведите одно целое число — минимальный урон, который Монокарп может получить, чтобы убить всех монстров в игре; если убить всех монстров невозможно, выведите -1.

Примеры
Входные данные
4
2 1 5 3
5 1 3 2
Выходные данные
4
Входные данные
4
3 1 5 3
5 1 3 2
Выходные данные
-1
Входные данные
3
1 1 1
1 2 3
Выходные данные
0
Входные данные
8
6 4 1 2 3 5 1 6
6 3 2 1 2 3 4 3
Выходные данные
16
Примечание

В первом примере Монокарп может действовать следующим образом:

$$$1$$$-й этап:

  • появляется $$$1$$$-й монстр;
  • Монокарп не может убить ни одного монстра;
  • $$$1$$$ живой монстр наносит $$$1$$$ урон, и общий урон, который получил Монокарп, равен $$$1$$$.
$$$2$$$-й этап:
  • появляется $$$2$$$-й монстр;
  • Монокарп убивает $$$2$$$-го монстра (используя элементальную атаку) и улучшает физический урон;
  • $$$1$$$ живой монстр наносит $$$1$$$ урон, и общий урон, который получил Монокарп, равен $$$2$$$.
$$$3$$$-й этап:
  • появляется $$$3$$$-й монстр;
  • Монокарп убивает $$$1$$$-го монстра (используя физическую атаку) и улучшает элементальный урон;
  • $$$1$$$ живой монстр наносит $$$1$$$ урон, и общий урон, который получил Монокарп, равен $$$3$$$.
$$$4$$$-й этап:
  • появляется $$$4$$$-й монстр;
  • Монокарп убивает $$$4$$$-го монстра (используя элементальную атаку) и улучшает элементальный урон;
  • $$$1$$$ живой монстр наносит $$$1$$$ урон, и общий урон, который получил Монокарп, равен $$$4$$$.
$$$5$$$-й этап:
  • Монокарп убивает $$$3$$$-го монстра (используя элементальную атаку) и улучшает физический урон;
  • все монстры убиты, и общий урон, который получил Монокарп, равен $$$4$$$.