MENGATUR BEBEK

 

Pak Dengklek berternak bebek. Ia memiliki sejumlah varietas (jenis) bebek yang ia ternakan. Jumlah bebek setiap varietas persis sama. Suatu hari Pak Dengklek hendak pergi mengangon para bebek. Bebek-bebek jika diangon suka berjalan membentuk barisan panjang satu-satu. Para bebek baru mau berjalan kalau barisan mereka sudah berada dalam pengurutan yang benar. Karena selama ini Pak Dengklek terlalu memanja para bebek itu, mereka menjadi malas untuk mengatur diri sendiri dan mereka menunggu diatur oleh Pak Dengklek. Pak Dengklek mengatur urutan barisan dengan mengangkat dan menyisipkan bebek-bebek pada urutan yang seharusnya.

Para bebek mempunyai aturan pengurutan barisan yang unik. Bebek-bebek dari varietas yang sama selalu berada dalam satu berderetan dan tidak mau terpisahkan, jadi selalu ingin berurutan. Dalam setiap varietasnya, bebek-bebek berbaris dari yang terkecil ke yang terbesar. Urutan antara varietas dalam barisan tidaklah penting. Berhubung hari sudah siang, Pak Dengklek harus mengatur bebek-bebek sesegera mungkin sehingga ia perlu urutan pemindahan sesedikit mungkin. Satu kali pemindahan adalah menarik mengangkat satu bebek (otomatis bebek-bebek di belakangnya maju mengisi ruang yang ditinggalkan) dan menyisipan di tempat baru (otomatis bebek-bebek di belakangnya mundur memberi ruang untuk ditempati).

Tuliskan program BEBEK.PAS yang dapat menemukan jumlah langkah pemindahan minimal untuk mengurutkan para bebek (ingat sebelumnya para bebek sudah berbaris yang mungkin belum terurut).

 

Format Masukan

 

Masukan adalah file bernama BEBEK.IN. Baris pertama berisi dua integer C dan N yang dipisahkan oleh satu spasi. C adalah jumlah varietas bebek (1 ≤ C ≤ 4), dan N adalah jumlah bebek dari setiap varietas (1 ≤ N ≤ 100).

Setiap dari C*N baris berikutnya terdapat pasangan dua bilangan integer X dan Y, 1 ≤ X ≤ C, 1 ≤ Y ≤ N, yang dipisahkan oleh satu spasi. X menyatakan nomor varietas dan Y menyatakan ukuran badan bebek. Urutan baris sesuai dengan urutan bebek dalam barisan mula-mula.

Tidak ada dua bebek dari varietas yang sama memiliki ukuran badan yang sama (dua baris memiliki data X dan Y yang sama).

 

Format Keluaran

 

Keluaran adalah file BEBEK.OUT. Keluaran hanya berisi satu bilangan yang menyatakan jumlah paling sedikit pemindahan bebek untuk menyusun para bebek sesuai dengan urutan yang dikehendaki sehingga mereka mau berjalan.

 

Contoh-contoh

 

BEBEK.IN

2 2

2 1

1 2

1 1

2 2

 

BEBEK.OUT

2

 

 

BEBEK.IN

4 1

2 1

3 1

1 1

4 1

 

BEBEK.OUT

0

 

 

BEBEK.IN

3 2

3 2

2 2

1 1

3 1

2 1

1 2

 

BEBEK.OUT

2