Nosaukums
Kartiņu pasjanss (cards)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
100%

Definīcija

Olimpijas novadā ir populārs sekojošs kartiņu pasjanss. Uz galda viena blakus otrai ir noliktas N krāsainu kartiņu kaudzītes. Ja vairāku blakus esošu kaudzīšu augšējās kartiņas ir vienā krāsā, tad tās visas drīkst noņemt vienā gājienā.

Uzrakstiet programmu, kas nosaka mazāko gājienu skaitu, kāds nepieciešams, lai noņemtu visas uz galda esošās kartiņas. 


Ievaddatu raksturojums

Ievaddatu pirmā rinda satur naturālus skaitli N 2 <=N , kas apzīmē kaudzīšu skaitu.
Katra i-tā no nākošajām N faila rindām satur naturālu skaitli K (K >=1), kas norāda kartiņu skaitu i-tajā kaudzītē un K naturālu skaitļu virknē, kas norāda kartiņu krāsu i-tajā kaudzītē, sākot no apakšējās. Katri divi blakus skaitļi ievadā ir atdalīti ar tukšumsimbolu. Zināms, ka 1<=N*K<=10000 un skaitlis, kas apzīmē krāsu ir robežās no 1 līdz 2*109.


Izvaddatu raksturojums

Izvaddatu vienīgajā rindā jāizvada mazākais gājienu skaits, kāds nepieciešams, lai noņemtu visas uz galda esošās kartiņas.


Piezīmes

Uzdevums izmantots Ukrainas XIII informātikas olimpiādē 2000.gadā.


Paraugdati

Stdin
2
2 1 2
3 3 1 2
Stdout
3

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