В космопорт "МК Ультра" прибыло N Неопознанных Летающих Тарелок. Чтобы опознать тарелки, их необходимо сначала помыть. Все тарелки сложены в стопку, высота тарелки номер i сверху равна Hi.
В космопорте работает две посудомоечных машины. Тогда и только тогда, когда одна из машин свободна, она может загрузить себе в буфер несколько последовательных тарелок сверху стопки. Буфер первой машины имеет высоту D1, а буфер второй — D2, в буфер нельзя поместить тарелок с суммарной высотой больше, чем высота буфера. Если в какой-то момент времени обе машины оказались свободны, они могут выполнить загрузку в любом порядке, но каждая из них — одной неделимой операцией.
Пока в буфере посудомоечной машины есть тарелки, она достает и моет их по одной. Пока все тарелки из буфера не будут помыты, машина считается занятой. Помытые тарелки отправляются на опознание и в процессе мытья больше не участвуют. Первая машина моет тарелку высотой Hi за S1 × Hi секунд, а вторая — за S2 × Hi секунд.
Необходимо определить, за какое минимальное время все тарелки могут быть помыты. Временем всех процессов кроме непосредственно мытья тарелки машинами можно пренебречь. При необходимости, машины могут простаивать какое-то время, если это минимизирует итоговый результат.
Первая строка содержит два целых числа S1 и S2 (1 ≤ S1, S2 ≤ 50).
Вторая строка содержит два целых числа D1 и D2 (1 ≤ D1, D2 ≤ 10000). Гарантируется, что любую тарелку возможно помыть в любой машине.
Третья строка содержит количество тарелок в стопке N (1 ≤ N ≤ 200).
В последней строке через пробел задано N целых чисел Hi (1 ≤ Hi ≤ 50) — высоты летающих тарелок, начиная сверху стопки.
Выведите одно целое число — минимальное количество секунд, которое пройдет с начала мойки до того момента, когда все тарелки будут отправлены на опознание.
4 3
14 11
10
1 2 3 9 5 2 7 3 2 8
72
В примере минимальное время могло быть достигнуто следующим образом:
