Ling se promène dans un centre commercial lorsqu'une machine à gashapon attire son attention. La machine contient $n$ types de gashapons, et il y a $a_i$ exemplaires du $i$-ème type.

• Dépenser une pièce de gashapon permet d'obtenir un gashapon au hasard.
• Dépenser $k$ gashapons quelconques permet d'obtenir une pièce spécifique auprès du commerçant.
• Dépenser une pièce spécifique permet d'obtenir un gashapon d'un type choisi dans la machine.

Les gashapons obtenus ne sont pas remis dans la machine. Ling souhaite collectionner les $n$ types de gashapons, c'est-à-dire en posséder au moins un de chaque type à la fin. Elle veut savoir combien de pièces de gashapon sont nécessaires au minimum pour garantir qu'elle puisse obtenir les $n$ types.

Entrée

Ce problème comporte plusieurs jeux de données. La première ligne contient un entier positif $T$ ($1 \le T \le 3000$), représentant le nombre de jeux de données.

Pour chaque jeu de données : La première ligne contient deux entiers positifs $n, k$ ($1 \le n \le 3000, 1 \le k \le 3 \times 10^5$), représentant respectivement le nombre de types de gashapons et le nombre de gashapons nécessaires pour obtenir une pièce spécifique. La deuxième ligne contient $n$ entiers positifs, où le $i$-ème entier est $a_i$ ($1 \le a_i \le 3000$), représentant la quantité du $i$-ème type de gashapon.

Il est garanti que la somme de $n$ sur l'ensemble des $T$ jeux de données ne dépasse pas $3000$.

Sortie

Pour chaque jeu de données : Afficher sur une ligne un entier représentant le nombre minimum de pièces de gashapon nécessaires pour garantir l'obtention des $n$ types de gashapons.

Exemples

Entrée 1

2
2 2
1 4
4 3
8 7 6 5

Sortie 1

3
9