maestru

Maestru

h2. Date de intrare

Pe prima linie a fisierului de intrare se gaseste T, numarul de teste. Pe prima linie a fiecarui test se afla numerele $N$ si $P$, urmand ca pe linia imediat urmatoare sa fie descris sirul sortat $x[~1~], x[~2~], … x[~N~]$.

Pe prima linie a fisierului de intrare se gaseste $T$, numarul de teste. Pe prima linie a fiecarui test se afla numerele $N$ si $P$, urmand ca pe linia imediat urmatoare sa fie descris sirul sortat $x[~1~], x[~2~], … x[~N~]$.

h2. Date de ieşire

In fisierul de iesire se vor afisa T linii, pe fiecare dintre acestea un intreg reprezetand numarul minim de pietre ce trebuiesc adaugate. Daca exista o configuratie prin care se pot adauga numarul minim de pietre indicat in asa fel incat maestrul sa-si poate realiza drumul, solutia se considera corecta.

In fisierul de iesire se vor afisa $T$ linii, pe fiecare dintre acestea un intreg reprezetand numarul minim de pietre ce trebuiesc adaugate. Daca exista o configuratie prin care se pot adauga numarul minim de pietre indicat in asa fel incat maestrul sa-si poate realiza drumul, solutia se considera corecta.

h2. Restricţii

* $1 ≤ T ≤ 4000$

* $3 ≤ N ≤ 5000$
* $3 ≤ P ≤ 10^9^$
* $1 ≤ x[~i~] ≤ 10^9^$

3 7
1 6 12
3 4

1 3 5

2 4 6

4 4
1 5 10 11
| 1