Монокарп — студент Берландского государственного университета. Из-за недавних изменений в системе образования Берландии, Монокарпу приходится изучать только один предмет — программирование.
Учебный семестр состоит из \(n\) дней, и чтобы не быть отчисленным, Монокарп должен заработать как минимум \(P\) баллов в течение этих \(n\) дней. Есть два способа заработать баллы — выполнение практических заданий и посещение лекций. За каждое выполненное практическое задание Монокарп получает \(t\) баллов, а за каждую посещенную лекцию — \(l\) баллов.
Практические задания становятся доступными «каждую неделю» по мере продвижения семестра: первое задание становится доступным в день \(1\) (и может быть выполнено в любой день с \(1\) по \(n\)), второе задание становится доступным в день \(8\) (и может быть выполнено в любой день с \(8\) по \(n\)), третье задание становится доступным в день \(15\), и так далее.
Каждый день с \(1\) по \(n\) проходит лекция, на которую может прийти Монокарп. И каждый день Монокарп выбирает, учиться ему сегодня или отдыхать весь день. Когда Монокарп решает учиться, он посещает лекцию и может выполнить не более \(2\) заданий, которые уже доступны и еще не выполнены. Если Монокарп отдыхает весь день, он пропускает лекцию и игнорирует задания.
Монокарп хочет иметь как можно больше выходных, то есть максимизировать количество дней, которые он может отдыхать. Помогите ему вычислить максимальное количество дней, которые он может отдыхать!
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное количество дней, которые Монокарп может отдыхать, не будучи отчисленным из университета.
Примечание
В первом наборе семестр длится \(1\) день, поэтому Монокарп должен посетить лекцию в день \(1\). Поскольку посещение одной лекции уже дает \(5\) баллов (\(5 \ge P\)), не имеет значения, выполнит ли Монокарп задание или нет.
Во втором наборе Монокарп может, например, учиться в дни \(8\) и \(9\): в день \(8\) он посетит лекцию за \(10^9\) баллов и выполнит два задания еще на \(5 \cdot 10^8 + 5 \cdot 10^8\) баллов. А в день \(9\) он посетит только лекцию еще на \(10^9\) баллов.
В третьем наборе Монокарп может, например, учиться только в день \(42\): посещение лекции дает ему \(1\) балл, а решение \(2\) из \(6\) доступных заданий дает ему еще \(2 \cdot 10\) баллов.
В четвертом наборе Монокарп должен посетить все лекции и выполнить все задания, чтобы получить \(8 \cdot 10 + 2 \cdot 20 = 120\) баллов.
В пятом наборе Монокарп может, например, учиться в дни: \(8\) — одна лекция и первое и второе задания; \(15\) — одна лекция и третье задание; \(22\) — одна лекция и четвертое задание; \(29\) — одна лекция и пятое задание; \(36\) — одна лекция и шестое задание.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 5 5 2
14 3000000000 1000000000 500000000
100 20 1 10
8 120 10 20
42 280 13 37
|
0
12
99
0
37
|