В саду мистера Китаюты посажено n бамбуков (бамбук — высокая, быстрорастущая тропическая трава с полым стволом). На настоящий момент высота i-го бамбука составляет h_i метров, и она увеличивается на a_i метров в конце каждого дня.

Вообще, мистер Китаюта терпеть не может бамбук. Он как-то попытался вырубить ростки, но потерпел неудачу — слишком крепкие стволы. Но мистер Китаюта не сдался. Он изобрёл волшебный молот, чтобы вогнать бамбук в землю.

За день можно использовать волшебный молот не более k раз, так как его волшебная сила не бесконечна. При каждом ударе волшебным молотом по бамбуку высота бамбука уменьшается на p метров. При этом высота бамбука не может стать отрицательной, то есть если его текущая высота меньше p, она становится равна 0 метрам (росток не исчезает). Иными словами, если ударить волшебным молотом по бамбуку высотой h метров, то новая высота ростка будет max(0, h - p) метров. Разрешается ударять по одному и тому же бамбуку более одного раза в день.

Мистер Китаюта будет сражаться с бамбуком m дней, начиная с сегодняшнего дня. Его цель — минимизировать высоту самого высокого бамбука через m дней (то есть, после последовательности из m повторений «Мистер Китаюта ударяет по росткам бамбука, и затем ростки растут»). Найдите наименьшую возможное значение высоты самого высокого бамбука через m дней.