Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

F. МК Ультра
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
128 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В космопорт "МК Ультра" прибыло 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
Примечание

В примере минимальное время могло быть достигнуто следующим образом:

  • в момент времени 0 первая машина загружает тарелку 1, вторая — 2;
  • в момент времени 4 первая машина загружает тарелку 3;
  • в момент времени 6 вторая машина загружает тарелку 4;
  • в момент времени 16 первая машина загружает тарелки 5 - 7;
  • в момент времени 33 вторая машина загружает тарелки 8 - 9;
  • в момент времени 48 вторая машина загружает тарелку 10.