Busy Beaver está tomando su primer examen en el Instituto de Tecnología de Pruebas Intensivas (MITIT). El examen es largo y el tiempo es limitado, por lo que necesita planificar una estrategia.
El examen dura $M$ minutos y consta de $N$ problemas. El $i$-ésimo problema tiene un valor de dificultad entero positivo, $d_i$. Un problema con dificultad $d$ toma $d$ minutos en resolverse y otorga $d+1$ puntos. No hay crédito parcial por completar una parte de un problema.
Además, si Busy Beaver entrega el examen $X$ minutos antes de que se agote el tiempo ($0 \le X \le M$), recibirá $X$ puntos de bonificación añadidos a su puntuación.
¿Cuál es la puntuación máxima posible que Busy Beaver puede obtener?
Entrada
Cada caso de prueba contiene múltiples casos de prueba. La primera línea contiene el número de casos de prueba $T$ ($1 \le T \le 10^4$). A continuación sigue la descripción de los casos de prueba.
La primera línea de cada caso de prueba contiene dos enteros $N$, $M$ ($1 \le N \le 10^5$, $1 \le M \le 10^9$).
La segunda línea de cada caso de prueba contiene $N$ enteros separados por espacios $d_1, \dots, d_N$ ($1 \le d_i \le 10^9$).
Se garantiza que la suma de $N$ sobre todos los casos de prueba no excede $10^5$.
Salida
Para cada caso de prueba, imprima un solo entero: la puntuación máxima posible.
Subtareas
- ($15$ puntos) Hay tiempo suficiente para terminar todos los problemas.
- ($15$ puntos) Todos los problemas tienen la misma dificultad.
- ($70$ puntos) Sin restricciones adicionales.
Ejemplos
Entrada 1
4 4 7 1 2 3 4 4 45 15 10 5 10 5 10 20 30 40 50 60 5 10 8 4 13 5 7
Salida 1
10 49 10 12
Nota
En el primer caso de prueba, Busy Beaver puede resolver los problemas con dificultades $1$, $2$ y $4$, en $7$ minutos. Busy Beaver obtendrá $2 + 3 + 5 = 10$ puntos de esta manera (sin puntos de bonificación, porque no queda tiempo extra).
En el segundo caso de prueba, Busy Beaver puede resolver los cuatro problemas con $5$ minutos de sobra, y obtener un total de $49$ puntos: $16 + 11 + 6 + 11 = 44$ puntos de los problemas, más $5$ puntos de bonificación.
En el tercer caso de prueba, ¡Busy Beaver no puede resolver ninguno de los problemas dentro del tiempo dado! Por lo tanto, lo mejor que puede hacer es entregar un examen en blanco justo después de que comience el cronómetro, lo que otorga $10$ puntos de bonificación.
En el cuarto caso de prueba, Busy Beaver puede resolver los dos problemas con dificultades $4$ y $5$, en $9$ minutos; Busy Beaver recibirá $1$ punto de bonificación ya que queda $1$ minuto restante, y obtendrá $5 + 6 + 1 = 12$ puntos en total.