Architekt Numernabis buduje pałac dla Cezara. Rzecz jasna, taki pałac powinien posiadać mnóstwo komnat, najlepiej każdą w innym kolorze. Nowoczesna sztuka urządzania pałaców nakazuje, aby kolory komnat sąsiadujących ze sobą możliwie najbardziej się różniły (w ten sposób przechodząc między komnatami Cezar nie będzie się nudził).

Numernabis ponumerował wszystkie kolory liczbami od 1 do m (m jest jednocześnie liczbą komnat i liczbą dostępnych kolorów) w taki sposób, że kolorom bardzo się od siebie różniącym odpowiadają bardzo się różniące liczby. Przy ustalonym kolorowaniu komnat pałacu można dla każdego przejścia między komnatami obliczyć różnicę wartości kolorów komnat, które to przejście łączy. Numernabis chce zmaksymalizować sumę takich różnic liczoną po wszystkich komnatach, przy czym każda komnata ma być pomalowana innym kolorem.

Pałac ma idealny kształt n-kąta foremnego, a każda z komnat jest wielokątem wypukłym, którego wierzchołki leżą na obwodzie pałacu (ostatni krzyk mody). Po ponumerowaniu wierzchołków pałacu liczbami 1..n (zgodnie z kierunkiem ruchu słońca, kiedy patrzeć na nie z dachu pałacu), każdą komnatę można opisać przez ciąg numerów jej wierzchołków.

Zadanie

Napisz program, który:

• wczyta z pliku tekstowego a.in opis komnat pałacu,
• znajdzie najlepszy układ kolorów komnat,
• zapisze odpowiednią sumę różnic wartości kolorów w pliku tekstowym a.out.

Wejście

W pierwszym wierszu pliku tekstowego a.in znajdują się dwie liczby całkowite n, m (1 <= n <= 50000, 1 <= m < n-2), będące odpowiednio liczbą zewnętrznych ścian pałacu oraz liczbą komnat. W każdym z kolejnych m wierszy znajduje się opis jednej komnaty (i+1-szy wiersz zawiera opis i-tej komnaty). Opis pojedynczej komnaty jest ciągiem liczb całkowitych pooddzielanych pojedynczymi odstępami. Pierwszym elementem tego ciągu jest liczba ścian komnaty, a pozostałe elementy to numery wierzchołków komnaty wymienione w kolejności rosnącej.

Wyjście

Plik tekstowy a.out powinien zawierać dokładnie jeden wiersz. Wiersz ten powinien zawierać tylko jedną liczbę całkowitą - największą możliwą sumę różnic wartości kolorów dla danego pałacu.

Przykład

Dla pliku wejściowego a.in:

7 4
3 1 2 3
3 1 3 5
4 1 5 6 7
3 3 4 5

poprawną odpowiedzią jest plik wyjściowy a.out:

6