portofel

Portofel

== include(page="template/taskheader" task_id="portofel") ==

Ai în portofel un teanc cu N bancnote, sortate crescător după valoare. După o extragere de la bancomat mai primeşti un teanc cu M bacnote, sortate şi ele după valoare. Vrei să le adaugi în portofel astfel încât la final să fie toate sortate. La o mutare poţi lua o secvenţă de bancnote consecutive dintre cele scoase din bancomat şi le poţi introduce la o anumita poziţie între cele din portofel, iar ordine dintre ele se păstrează. Care este numărul minim de mutări?

Ai în portofel un teanc cu **N** bancnote, ordonate crescător după valoare. După o extragere de la bancomat mai primeşti un teanc cu **M** bancnote, ordonate şi ele după valoare. Vrei să le adaugi în portofel astfel încât la final să fie toate ordonate crescător. La o mutare poţi lua o secvenţă de bancnote consecutive dintre cele scoase din bancomat şi le poţi introduce la o anumita poziţie între cele din portofel, iar ordinea dintre ele se păstrează. Care este numărul minim de mutări pentru a adăuga toate bancnotele în portofel?

h2. Date de intrare

Fişierul de intrare $portofel.in$ conţine pe primia linie numărul de teste T. Pentru fiecare test în ordine sunt scrise, pe câte trei linii configuraţiile testelor. Pe prima linie sunt scrise numerele N şi M. Următoarea linie conţine valorile bancnotelor care sunt iniţial în portofel, iar pe următoarea linie sunt scrise valorile bancnotelor scoase din bancomat.

Fişierul de intrare $portofel.in$ conţine pe primia linie numărul de teste **T**. Apoi, pentru fiecare test în ordine, sunt scrise pe câte trei linii configuraţiile testelor. Pe prima linie sunt scrise numerele **N** şi **M**. Următoarea linie conţine valorile bancnotelor care sunt iniţial în portofel, iar pe următoarea linie sunt scrise valorile bancnotelor scoase din bancomat.

h2. Date de ieşire

În fişierul de ieşire $portofel.out$ afişaţi T linii cu răspunsurile pentru fiecare test, în ordine.

În fişierul de ieşire $portofel.out$ afişaţi **T** linii cu răspunsurile pentru fiecare test, în ordine.

h2. Restricţii

* 1 ≤ T, M ≤ 5$
* 1 ≤ N, M ≤ 100000$
* 1 ≤ valorile bancnotelor ≤ 1000000000$

* 1 ≤ **T** ≤ 5
* 1 ≤ **N**, **M** ≤ 10^5^
* 1 ≤ valorile bancnotelor ≤ 10^9^

h2. Exemplu

8 6
1 1 1 5 5 100 100 100
1 1 5 100 100 500

9 6

9 5

1 1 1 5 5 100 100 100 200
1 1 100 100 500
| 2
3
| Pentru primul caz se pot muta primele 3 bancnote iar la a doua mutare ultimele 3.

La final în portofel vor fi: 1 1 1 [1 1 5] 5 5 100 100 100 [100 100 500];

La final în portofel vor fi: 1, 1, 1, [1, 1, 5,] 5, 5, 100, 100, 100, [100, 100, 500],

unde între paranteze pătrate sunt bancnotele din bancomat.

Pentru al doilea caz este nevoie de 3 mutări, de exemplu: 1 [1 1] 1 1 5 5 [100 100] 100 100 100 200 [500].

Pentru testul doi e nevoie de 3 mutări, de exemplu: 1, [1, 1,] 1, 1, 5, 5, [100, 100,] 100, 100, 100, 200, [500].

|

h3. Explicaţie
 
Pentru primul caz se pot muta primele 3 bancnote iar la a doua mutare ultimele 3. La final în portofel vor fi: 1 1 1 [1 1 5] 5 5 100 100 100 [100 100 500], unde între paranteze pătrate sunt bancnotele din bancomat.
Pentru al doilea caz este nevoie de 3 mutări, de exemplu: 1 [1 1] 1 1 5 5 [100 100] 100 100 100 200 [500].
 

== include(page="template/taskfooter" task_id="portofel") ==