Debido a circunstancias impredecibles, se decide comprar azúcar por adelantado. Hay n tiendas que venden azúcar: la tienda i ofrece un paquete a precio ai, con la limitación de un paquete por cliente al día. Para adquirir varios paquetes, es necesario visitar múltiples tiendas. Un desafío adicional es que los precios aumentan diariamente: el primer día el costo es ai, el segundo día ai+1+1, el tercer día ai+2+2, y así sucesivamente para cada tienda i.

El presupuesto diario disponible es de x monedas. Cada día, se compran tentos paquetes como sea posible sin exceder el costo total x. Las monedas no gastadsa no se acumulan para días posteriores. Eventualmente, el precio mínimo de un paquete superará x, y no se podrá comprar ninguno. El objetivo es determinar el número total de paquetes que se pueden adquirir hasta ese momento.

Formato de Entrada

La primera línea contiene un entero t (1 ≤ t ≤ 1000) que indica el número de casos de prueba. Cada caso consta de dos líneas:

• La primera línea de cada caso contiene dos enteros n y x (1 ≤ n ≤ 2·10^5; 1 ≤ x ≤ 10^9), donde n es el número de tiendas y x el presupuesto diario.
• La segunda línea contiene n enteros a1, a2, ..., an (1 ≤ ai ≤ 10^9), que representan el precio inicial de un paquete en cada tienda.

Se garantiza que la suma total de n en todos los casos no excede 2·10^5.

Formato de Salida

Para cada caso de prueba, se imprime un entero: el total de paquetes comprados hasta que los preccios excedan el presupuesto diario.

Ejemplo

Entrada:

4
3 7
2 1 2
5 9
10 20 30 40 50
1 1
1
2 1000
1 1

Salida:

11
0
1
1500

Explicación del Ejemplo

En el primer caso:

• Día 1: precios [2,1,2]. Se compran los 3 paquetes ya que 2+1+2 ≤ 7.
• Día 2: precios [3,2,3]. No se pueden comprar todos, se adquieren 2 paquetes.
• Día 3: precios [4,3,4]. Se compran 2 paquetes con costos 4 y 3.
• Día 4: precios [5,4,5]. Solo se puede comprar 1 paquete.
• Día 5: precios [6,5,6]. Se compra 1 paquete.
• Día 6: precios [7,6,7]. Se compra 1 paquete.
• Día 7: precios [8,7,8]. Aún se compra 1 paquete de costo 7.
• Día 8: precios [9,8,9]. Los precios son demasiado altos, no se compra nada.

Total: 3+2+2+1+1+1+1 = 11 paquetes. En el segundo caso, los precios ya son demasiado altos el primer día. En el tercer caso, solo se compra un paquete el día uno.

Solución en C++

A continuación se presenta una implementación en C++ que utiliza un enfoque codicioso con sumas de prefijos:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        ll x;
        cin >> n >> x;
        vector<ll> precios(n);
        for (int i = 0; i < n; i++) {
            cin >> precios[i];
        }
        sort(precios.begin(), precios.end());
        vector<ll> prefijo(n+1, 0);
        for (int i = 0; i < n; i++) {
            prefijo[i+1] = prefijo[i] + precios[i];
        }
        ll total_paquetes = 0;
        ll dias_transcurridos = 0;
        for (int i = n; i >= 1; i--) {
            if (prefijo[i] + dias_transcurridos * i > x) {
                continue;
            }
            ll dias_posibles = (x - prefijo[i] - dias_transcurridos * i) / i + 1;
            total_paquetes += dias_posibles * i;
            dias_transcurridos += dias_posibles;
        }
        cout << total_paquetes << endl;
    }
    return 0;
}