C. Антон и зельеварение
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Антон играет в одну очень интересную компьютерную игру, и сейчас он застрял на одном из уровней. Чтобы пройти на следующий уровень, Антону надо приготовить n зелий.

У Антона в распоряжении есть котёл, который может сварить одно зелье за х секунд. Дополнительно, имеются заклинания двух типов, которые помогают ускорить процесс приготовления зелий:

  1. Заклинания этого типа ускоряют приготовление в котле одного зелья. Всего существует m таких заклинаний, i-е из них стоит bi единиц маны и делает так, чтобы каждое зелье варилось ai секунд вместо x.
  2. Заклинания этого типа варят несколько зелий мгновенно. Всего существует k таких заклинаний, i-е из которых стоит di единиц маны и мгновенно варит ci зелий.

Антон может использовать не более одного заклинания первого вида и не более одного заклинания второго вида, при этом суммарная стоимость заклинаний не должна превышать s единиц маны. Считается, что заклинания используются мгновенно и непосредственно перед началом варки зелий.

Антон хочет как можно быстрее перейти на следующий уровень, поэтому ему интересно, за какое минимальное время можно сварить не менее n зелий.

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

В первой строке входных данных находятся три целых числа n, m, k (1 ≤ n ≤ 2·109, 1 ≤ m, k ≤ 2·105) — количество зелий, которые надо сварить, количество заклинаний первого и количество заклинаний второго типа соответственно.

Во второй строке входных данных находятся два целых числа x и s (2 ≤ x ≤ 2·109, 1 ≤ s ≤ 2·109) — время варки одного зелья и количество единиц маны соответственно.

В третьей строке даны m целых чисел ai (1 ≤ ai < x) — время, за которое будет вариться одно зелье, если использовать i-е заклинание первого вида.

В четвертой строке записаны m целых чисел bi (1 ≤ bi ≤ 2·109) — стоимость i-го заклинания первого вида в единицах маны.

В пятой строке находятся k целых чисел ci (1 ≤ ci ≤ n) — количество зелий, которое будет сварено мгновенно при использовании i-го заклинания второго типа. Гарантируется, что ci упорядочены по неубыванию, то есть ci ≤ cj, если i < j.

В шестой строке входных данных находятся k целых чисел di (1 ≤ di ≤ 2·109) — стоимость i-го заклинания второго типа в единицах маны. Гарантируется, что di упорядочены по неубыванию, то есть di ≤ dj, если i < j.

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

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

Примеры
Входные данные
20 3 2
10 99
2 4 3
20 10 40
4 15
10 80
Выходные данные
20
Входные данные
20 3 2
10 99
2 4 3
200 100 400
4 15
100 800
Выходные данные
200
Примечание

В первом примере выгоднее всего будет применить второе заклинание первого типа, которое стоит 10 единиц маны. В таком случае каждое зелье будет вариться 4 секунды. Также мы используем второе заклинание второго типа, чтобы мгновенно сварить 15 зелий за 80 единиц маны. Итого мы потратим 10 + 80 = 90 единиц маны, а все зелья сварятся за 4·5 = 20 секунд (так как 15 зелий мы сварили мгновенно, а оставшиеся 5 будут вариться по 4 секунды).

Во втором примере все заклинания стоят больше единиц маны, чем у нас есть, поэтому мы не можем использовать ни одно из заклинаний. Мы просто варим 20 зелий по 10 секунд каждое, и ответ равен 20·10 = 200 секунд.