Nosaukums
Kāršu kārtošana (cards2)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
50%

Definīcija

Mazajam Maverikam patīk spēlēt kārtis, bet lielas raizes viņam sagādā kāršu sakārtošana rokā. Kad Maveriks ir pacēlis sev pienākošās kārtis, viņš vispirms tās sakārto grupās tā, lai katrā grupā būtu visas vienas krāsas kārtis. Pēc tam viņš sakārto kārtis katrā grupā pēc to vērtības - kārtij ar zemāku vērtību grupā jāatrodas vairāk pa kreisi. Protams, ka šo kārtošanu laikā visas kārtis jātur rokā.

Maveriks vēlas sakārtot kārtis cik ātri vien iespējams, t.i., izdarot pēc iespējas mazāk gājienu. "Gājiens" ir vienas kārts pārvietošana.

Uzrakstiet programmu, kas nosaka, kāds ir mazākais iespējamais gājienu skaits!


Ievaddatu raksturojums

Ievaddatu pirmā rinda satur divu naturālu skaitļu C(dažādo krāsu skaits,1 ≤C≤4) un N(vienas krāsas kāršu skaits, 1≤N≤100) vērtības, kas atdalītas ar tukšumsimbolu.

Katra no nākošajām C*N faila rindām satur pa diviem naturāliem skaitļiem X un Y, 1≤X≤C, 1≤Y≤N, kas atdalīti ar tukšumsimbolu. Katrs šāds skaitļu pāris apzīmē vienas kārts krāsu (X) un vērtību(Y). Kāršu secība ir tāda, kādā kārtis Maveriks ir tās pacēlis.

Visas kārtis savā starpā ir dažādas.


Izvaddatu raksturojums

Izvaddatu vienīgajā rindā jāizvada vesels skaitlis - mazākais gājienu skaits, kāds nepieciešams, lai kārtis sakārtotu.


Piezīmes

Uzdevums izmantots Horvātijas informātikas olimpiādē 2001.gadā


Paraugdati

Stdin
2 2
2 1
1 2
1 1
2 2
Stdout
2

Stdin
4 1
2 1
3 1
1 1
4 1
Stdout
0

Stdin
3 2
3 2
2 2
1 1
3 1
2 1
1 2
Stdout
2

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.