В линию выстроены $$$n$$$ монстров, пронумерованных числами с $$$1$$$ по $$$n$$$. У $$$i$$$-го монстра есть $$$h_i$$$ очков здоровья (hp). Вы можете атаковать с силой, равной $$$a$$$ hp, а ваш соперник может атаковать с силой, равной $$$b$$$ hp.

Вы и ваш соперник сражаетесь с этими монстрами. Сначала вы и ваш соперник идете к первому монстру и сражаетесь с ним до тех пор, пока он не будет мертв, затем вы и ваш соперник отправляетесь ко второму монстру и сражаетесь с ним до тех пор, пока и он не будет мертв, и так далее. Смерть монстра наступает, когда значение его hp становится меньшим или равным $$$0$$$.

Сражение с монстром происходит поочередно.

1. Вы атакуете монстра с силой $$$a$$$ hp. Если он погибает после вашего удара, вы получаете одно очко и затем вы и соперник переходите к следующему монстру.
2. Ваш соперник атакует монстра с силой $$$b$$$ hp. Если монстр погибает после этой атаки, никто не получает очко и вы с соперником переходите к следующему монстру.

У вас есть некоторая секретная техника, с помощью которой можно заставить вашего соперника пропустить свой ход. Вы можете использовать эту технику не более, чем $$$k$$$ раз всего (например, если есть два монстра и $$$k=4$$$, то вы можете использовать эту технику $$$2$$$ раза во время сражения с первым монстром и $$$1$$$ один раз — со вторым, но не $$$2$$$ раза с первым монстром и $$$3$$$ раза со вторым).

Ваша задача — определить максимальное число очков, которое вы можете получить, если будете использовать секретную технику оптимально.