Задача C. Деревья Илона Маска ≡

Условие

Девочка Саша устроилась волонтёром в благотворительный фонд Илона Маска, который занимается посадкой деревьев.

Каждый месяц фонд получает M денежных средств, которые тратит на посадку и заботу об уже посаженных деревьях. Все не потраченные деньги изымаются в конце месяца. В самом начале посадка дерева стоит K денег, но из-за кризиса стоимость растёт на P каждый месяц. Обслуживание каждого посаженного дерева стоит L денег в месяц, при этом стоимость обслуживания уменьшается ежемесячно после первого на R, пока не достигнет нуля. В первый раз дерево обслуживается на следующий месяц после посадки, т.е. стоимость обслуживания дерева в первый месяц L, во второй L−R, потом L−2∗R и так далее. Стоимость обслуживания дерева зависит от времени, когда оно было посажено.

Цель фонда —- посадить (но не обязательно вырастить) T деревьев. Это означает, что допустимо в последний месяц высадить столько деревьев, что денег в следующий месяц не хватит на обслуживание деревьев, но до момента, пока все деревья не высажены, нельзя тратить больше, чем M денег в месяц. Саше поручили написать программу, которая рассчитает минимальное количество месяцев, которое понадобится для достижения цели. Саша попросила вас помочь ей с этим.

Формат входных данных

Входные данные содержат число M — ежемесячное количество выделяемых денежных средств, K — стоимость посадки дерева, P — на сколько увеличится стоимость посадки, L — стоимость обслуживания дерева, R — на сколько уменьшится стоимость обслуживания, T — требуемое количество деревьев.

Формат выходных данных

Выходные данные должны содержать одно целое число: минимальное количество месяцев, которое требуется для посадки T деревьев. В случае, если высадить деревья невозможно выведите −1.

Ограничения

1 ≤ M, T, L, K ≤ 10⁴

1 ≤ P, R ≤ 10²

Описание подзадач и системы оценивания

Баллы начисляются пропорционально количеству пройденных тестов. Каждый тест оценивается в 4 балла.

Примеры тестов

100 5 1 4 1 40

6