В линию выстроены \(n\) монстров, пронумерованных числами с \(1\) по \(n\). У \(i\)-го монстра есть \(h_i\) очков здоровья (hp). Вы можете атаковать с силой, равной \(a\) hp, а ваш соперник может атаковать с силой, равной \(b\) hp.
Вы и ваш соперник сражаетесь с этими монстрами. Сначала вы и ваш соперник идете к первому монстру и сражаетесь с ним до тех пор, пока он не будет мертв, затем вы и ваш соперник отправляетесь ко второму монстру и сражаетесь с ним до тех пор, пока и он не будет мертв, и так далее. Смерть монстра наступает, когда значение его hp становится меньшим или равным \(0\).
Сражение с монстром происходит поочередно.
- Вы атакуете монстра с силой \(a\) hp. Если он погибает после вашего удара, вы получаете одно очко и затем вы и соперник переходите к следующему монстру.
- Ваш соперник атакует монстра с силой \(b\) hp. Если монстр погибает после этой атаки, никто не получает очко и вы с соперником переходите к следующему монстру.
У вас есть некоторая секретная техника, с помощью которой можно заставить вашего соперника пропустить свой ход. Вы можете использовать эту технику не более, чем \(k\) раз всего (например, если есть два монстра и \(k=4\), то вы можете использовать эту технику \(2\) раза во время сражения с первым монстром и \(1\) один раз — со вторым, но не \(2\) раза с первым монстром и \(3\) раза со вторым).
Ваша задача — определить максимальное число очков, которое вы можете получить, если будете использовать секретную технику оптимально.
Выходные данные
Выведите одно целое число — максимальное число очков, которое вы можете получить, если будете использовать секретную технику оптимально.