Codeforces Round 946 (Div. 3) |
---|
Закончено |
Никогда нельзя купить достаточно счастья, поэтому мы снова здесь! В этой версии вы можете купить только $$$h_i = 1$$$ единицу счастья каждый месяц, но количество месяцев увеличено в разы. Мы находимся в области квантового счастья и временного растяжения.
Будучи физиком, Чарли любит планировать свою жизнь в простых и точных терминах.
В течение следующих $$$m$$$ месяцев, начиная с нулевой суммы денег, Чарли будет усердно работать и зарабатывать $$$x$$$ фунтов в месяц. Для $$$i$$$-го месяца $$$(1 \le i \le m)$$$ будет одна возможность заплатить стоимость $$$c_i$$$ фунтов за получение одной единицы счастья. Вы не можете купить более одной единицы счастья каждый месяц.
Запрещено брать в долг. Деньги, заработанные в $$$i$$$-м месяце, могут быть потрачены только в более поздний $$$j$$$-й месяц ($$$j>i$$$).
Поскольку физики не пишут код, помогите Чарли найти максимально достижимое количество единиц счастья.
Первая строка ввода содержит $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора содержит два целых числа, $$$m$$$ и $$$x$$$ ($$$1 \le m \le 2 \cdot 10^5$$$, $$$1 \le x \le 10^3$$$) — общее количество месяцев и ежемесячная зарплата.
Вторая строка каждого набора содержит $$$m$$$ целых чисел $$$c_1, c_2, \dots, c_m$$$ ($$$1 \leq c_i \leq 10^3$$$) — стоимость одной единицы счастья для каждого месяца.
Гарантируется, что сумма $$$m$$$ по всем наборам входных данных теста не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — максимальное количество счастья, которое может получить Чарли.
63 32 2 26 52 2 8 2 6 86 44 10 3 8 6 102 11 14 14 1 3 14 21 3 4 3
2 4 3 1 2 1
Название |
---|