Taking an Exam

Busy Beaver passe son premier examen au Maximally Intensive Testing Institute of Technology (MITIT). L'examen est long et le temps est limité, il doit donc planifier une stratégie.

L'examen dure $M$ minutes et comporte $N$ problèmes. Le $i^\text{ème}$ problème a une difficulté représentée par un entier positif $d_i$. Un problème de difficulté $d$ prend $d$ minutes à résoudre et rapporte $d+1$ points. Aucun crédit partiel n'est accordé pour la résolution partielle d'un problème.

De plus, si Busy Beaver rend sa copie $X$ minutes avant la fin du temps imparti ($0 \le X \le M$), il recevra $X$ points bonus ajoutés à son score.

Quel est le score maximum que Busy Beaver peut obtenir ?

Entrée

Chaque test contient plusieurs cas de test. La première ligne contient le nombre de cas de test $T$ ($1 \le T \le 10^4$). La description des cas de test suit.

La première ligne de chaque cas de test contient deux entiers $N$ et $M$ ($1 \le N \le 10^5$, $1 \le M \le 10^9$).

La deuxième ligne de chaque cas de test contient $N$ entiers séparés par des espaces $d_1, \dots, d_N$ ($1 \le d_i \le 10^9$).

Il est garanti que la somme de $N$ sur tous les cas de test ne dépasse pas $10^5$.

Sortie

Pour chaque cas de test, affichez un seul entier : le score maximum possible.

Notation

• ($15$ points) Il y a suffisamment de temps pour terminer tous les problèmes.
• ($15$ points) Tous les problèmes ont la même difficulté.
• ($70$ points) Aucune contrainte supplémentaire.

Exemples

Entrée 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

Sortie 1

10
49
10
12

Remarque

Dans le premier cas de test, Busy Beaver peut résoudre les problèmes de difficultés $1$, $2$ et $4$ en $7$ minutes. Busy Beaver obtiendra $2 + 3 + 5 = 10$ points de cette manière (aucun point bonus, car il ne reste aucun temps supplémentaire).

Dans le deuxième cas de test, Busy Beaver peut résoudre les quatre problèmes avec $5$ minutes d'avance et obtenir un total de $49$ points : $16 + 11 + 6 + 11 = 44$ points provenant des problèmes, plus $5$ points bonus.

Dans le troisième cas de test, Busy Beaver ne peut résoudre aucun des problèmes dans le temps imparti ! La meilleure chose à faire est donc de rendre une copie blanche juste après le début de l'épreuve, ce qui donne $10$ points bonus.

Dans le quatrième cas de test, Busy Beaver peut résoudre les deux problèmes de difficultés $4$ et $5$ en $9$ minutes ; Busy Beaver recevra $1$ point bonus puisqu'il reste $1$ minute, et obtiendra $5 + 6 + 1 = 12$ points au total.