D. Берляндская ярмарка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

XXI Ежегодная Всеберляндская ярмарка уже совсем на носу! Традиционно ярмарка включает в себя $$$n$$$ киосков, расположенных по кругу. Киоски пронумерованы от $$$1$$$ до $$$n$$$ по часовой стрелке, киоск номер $$$n$$$ стоит рядом с номером $$$1$$$. В $$$i$$$-м киоске продаются конфеты по цене $$$a_i$$$ бурлей за штуку. В каждом киоске неограниченный запас конфет.

Поликапр решил потратить не более $$$T$$$ бурлей на ярмарке. Однако, у него также есть план, как он будет перемещаться между киосками:

  • сначала он посещает киоск номер $$$1$$$;
  • если у него хватает бурлей на покупку ровно одной конфеты в текущем киоске, то он ее сразу же покупает;
  • далее он переходит к следующему киоску по часовой стрелке (вне зависимости от того, купил ли он конфету или нет).

У Поликарпа конечное количество бурлей, поэтому процесс закончится, как только он не сможет купить конфету ни в одном киоске.

Посчитайте количество конфет, которые купит Поликарп.

Входные данные

В первой строке записаны два целых числа $$$n$$$ и $$$T$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le T \le 10^{18}$$$) — количество киосков на ярмарке и начальное количество бурлей у Поликарпа.

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — цена одной конфеты в киоске номер $$$i$$$.

Выходные данные

Выведите одно целое число — итоговое количество конфет, которые купит Поликарп.

Примеры
Входные данные
3 38
5 2 5
Выходные данные
10
Входные данные
5 21
2 4 100 2 6
Выходные данные
6
Примечание

Рассмотрим первый пример. Какие ходы делал Поликарп, пока у него не закончились деньги:

  1. Киоск $$$1$$$, покупает конфету за $$$5$$$, $$$T = 33$$$;
  2. Киоск $$$2$$$, покупает конфету за $$$2$$$, $$$T = 31$$$;
  3. Киоск $$$3$$$, покупает конфету за $$$5$$$, $$$T = 26$$$;
  4. Киоск $$$1$$$, покупает конфету за $$$5$$$, $$$T = 21$$$;
  5. Киоск $$$2$$$, покупает конфету за $$$2$$$, $$$T = 19$$$;
  6. Киоск $$$3$$$, покупает конфету за $$$5$$$, $$$T = 14$$$;
  7. Киоск $$$1$$$, покупает конфету за $$$5$$$, $$$T = 9$$$;
  8. Киоск $$$2$$$, покупает конфету за $$$2$$$, $$$T = 7$$$;
  9. Киоск $$$3$$$, покупает конфету за $$$5$$$, $$$T = 2$$$;
  10. Киоск $$$1$$$, не покупает конфету, недостаточно денег;
  11. Киоск $$$2$$$, покупает конфету за $$$2$$$, $$$T = 0$$$.

Больше нельзя купить конфет. Итоговое число купленных конфет — $$$10$$$.

Во втором примере у него остается $$$1$$$ бурль после посещения киосков, нельзя купить ни одну конфету за столько.