Wakacje [A]
Limit pamięci: 128 MB
Bajtazar wybiera się na wakacje do Bajtlandii.
Właśnie planuje swój pobyt i zastanawia się, które spośród tamtejszych atrakcji najbardziej chciałby zobaczyć.
Znalazł w internecie parę przewodników po Bajtlandii, w których znajdują się rankingi wszystkich atrakcji.
Na ich podstawie Bajtazar postanowił utworzyć własny ranking.
Atrakcje są ponumerowane od do .
Każdy ranking to ciąg zawierający liczby od do ustawione w kolejności od najciekawszej do najmniej ciekawej atrakcji.
Odległość pomiędzy dwoma rankingami obliczamy następująco.
Dla każdej atrakcji znajdujemy pozycje, na których występuje ona w pierwszym i drugim ciągu ( i ).
Następnie obliczamy wartość .
W ten sposób dla każdej atrakcji otrzymujemy jedną liczbę, która wskazuje, w jakim stopniu dwa rankingi różnią się w ocenie danej atrakcji.
Odległością dwóch rankingów jest suma tak uzyskanych liczb dla wszystkich atrakcji.
Bajtazar chce teraz skonstruować taki ranking, by jego sumaryczna odległość od wszystkich rankingów znalezionych w internecie była jak najmniejsza.
Wejście
Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite i (, ), oznaczające liczbę atrakcji w Bajtlandii oraz liczbę stron z rankingami atrakcji, które odwiedził Bajtazar.
Każdy z kolejnych wierszy opisuje ranking zamieszczony na jednej ze stron.
Każdy ranking podany jest w postaci ciągu liczb z zakresu od do , w którym każda liczba występuje dokładnie raz.
Atrakcje wymienione są w kolejności od najbardziej do najmniej polecanej.
Wyjście
Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą równą minimalnej sumarycznej odległości rankingu Bajtazara od zestawień podanych na stronach internetowych.
Przykład
Dla danych wejściowych:
5 2
5 2 4 3 1
2 4 1 3 5
poprawną odpowiedzią jest:
8
Wyjaśnienie do przykładu: Rankingami minimalizującymi sumę odległości od podanych
w przykładzie są, między innymi, 2 4 5 3 1 i 5 2 4 3 1.
Autor zadania: Piotr Sankowski (treść: Jakub Łącki).