XXI Ежегодная Всеберляндская ярмарка уже совсем на носу! Традиционно ярмарка включает в себя \(n\) киосков, расположенных по кругу. Киоски пронумерованы от \(1\) до \(n\) по часовой стрелке, киоск номер \(n\) стоит рядом с номером \(1\). В \(i\)-м киоске продаются конфеты по цене \(a_i\) бурлей за штуку. В каждом киоске неограниченный запас конфет.
Поликапр решил потратить не более \(T\) бурлей на ярмарке. Однако, у него также есть план, как он будет перемещаться между киосками:
- сначала он посещает киоск номер \(1\);
- если у него хватает бурлей на покупку ровно одной конфеты в текущем киоске, то он ее сразу же покупает;
- далее он переходит к следующему киоску по часовой стрелке (вне зависимости от того, купил ли он конфету или нет).
У Поликарпа конечное количество бурлей, поэтому процесс закончится, как только он не сможет купить конфету ни в одном киоске.
Посчитайте количество конфет, которые купит Поликарп.
Выходные данные
Выведите одно целое число — итоговое количество конфет, которые купит Поликарп.
Примечание
Рассмотрим первый пример. Какие ходы делал Поликарп, пока у него не закончились деньги:
- Киоск \(1\), покупает конфету за \(5\), \(T = 33\);
- Киоск \(2\), покупает конфету за \(2\), \(T = 31\);
- Киоск \(3\), покупает конфету за \(5\), \(T = 26\);
- Киоск \(1\), покупает конфету за \(5\), \(T = 21\);
- Киоск \(2\), покупает конфету за \(2\), \(T = 19\);
- Киоск \(3\), покупает конфету за \(5\), \(T = 14\);
- Киоск \(1\), покупает конфету за \(5\), \(T = 9\);
- Киоск \(2\), покупает конфету за \(2\), \(T = 7\);
- Киоск \(3\), покупает конфету за \(5\), \(T = 2\);
- Киоск \(1\), не покупает конфету, недостаточно денег;
- Киоск \(2\), покупает конфету за \(2\), \(T = 0\).
Больше нельзя купить конфет. Итоговое число купленных конфет — \(10\).
Во втором примере у него остается \(1\) бурль после посещения киосков, нельзя купить ни одну конфету за столько.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 38
5 2 5
|
10
|
|
2
|
5 21
2 4 100 2 6
|
6
|