B. Выборы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Берляндии регулярно проходят выборы президента. На любых выборах в Берляндии бывают фальсификации. И вот, на очередных выборах так сложилось, что все проголосовали против нужного вам кандидата. Вам нужно обеспечить победу вашего кандидата, но проблема в том, что слишком явные фальсификации вызывают народное недовольство.

Всего в Берляндии $$$n$$$ избирательных участков, на $$$i$$$-м из них $$$k_i$$$ избирателей, из них проголосовало $$$a_i$$$ (все против). Вам доступно два типа фальсификаций:

  • Вброс голосов за пенсионеров. На $$$i$$$-м участке можно сделать максимум $$$b_i$$$ таких вбросов, каждый из них увеличивает количество голосов за нужного вам кандидата на 1, но увеличивает народное недовольство на $$$x$$$.
  • Подмена голосов. На $$$i$$$-м участке можно сделать максимум $$$a_i$$$ подмен. Каждая подмена увеличивает количество голосов за нужного вам кандидата на 1, при этом, если на участке было сделано всего $$$y$$$ подмен, народное недовольство увеличивается на $$$y^2$$$.

Кандидат считается победителем, если процент голосов за него строго больше половины от общего количества избирателей (не только проголосовавших, но всех вообще).

Определите, можете ли вы обеспечить победу своего кандидата, и если да, то с каким минимальным народным недовольством вы можете это сделать.

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

Первая строка входных данных содержит целое число $$$n\ (1 \le n \le 10^5)$$$ — количество избирательных участков.

Вторая строка содержит $$$n$$$ целых чисел $$$k_1$$$, $$$k_2$$$, ..., $$$k_n$$$ — общее количество избирателей на каждом участке ($$$0\le k_i \le 10^4$$$).

Третья строка содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ — количество проголосовавших на каждом участке ($$$0\le a_i \le 10^4$$$).

Четвертая строка содержит $$$n$$$ целых чисел $$$b_1$$$, $$$b_2$$$, ..., $$$b_n$$$ — максимально возможное количество фальсификаций первого типа на каждом участке ($$$0\le b_i \le 10^4$$$).

Пятая строка содержит единственное целое число $$$x$$$ — увеличение недовольства при совершении одной фальсификации первого типа ($$$1\le x \le 10^8$$$).

Гарантируется, что $$$a_i + b_i\le k_i$$$ для всех $$$i$$$.

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

Выведите единственное целое число — минимально возможное недовольство, необходимое для победы вашего кандидата, или $$$-1$$$, если это невозможно.

Примеры
Входные данные
3
14 9 8
10 5 3
4 4 5
4
Выходные данные
52
Входные данные
2
20 10
9 4
1 0
5
Выходные данные
-1