Олимпиадный тренинг

Задача . C. Антон и зельеварение

Задача

Темы: Бинарный поиск два указателя дп жадные алгоритмы *1600

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

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

Заклинания этого типа ускоряют приготовление в котле одного зелья. Всего существует m таких заклинаний, i-е из них стоит b_i единиц маны и делает так, чтобы каждое зелье варилось a_i секунд вместо x.
Заклинания этого типа варят несколько зелий мгновенно. Всего существует k таких заклинаний, i-е из которых стоит d_i единиц маны и мгновенно варит c_i зелий.

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

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

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

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

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

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

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

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

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

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

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

Примечание

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

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

Примеры

№	Входные данные	Выходные данные
1	20 3 2 10 99 2 4 3 20 10 40 4 15 10 80	20
2	20 3 2 10 99 2 4 3 200 100 400 4 15 100 800	200

time 4000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	4

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет