8605번 - Waga 다국어

Mały Bajtek dostał od rodziców interesującą zabawkę. Składa się ona z wagi szalkowej oraz odważników w postaci cegiełek. Niektóre z nich są magiczne i mają ujemne wagi. Za pomocą tej zabawki Bajtek wyznaczał wagi przeróżnych przedmiotów. Jednak taka zabawa szybko mu się znudziła, więc wymyślił następującą grę.

Gra zaczyna się od ustawienia cegiełek na obu szalkach wagi, tak aby utworzyły pewną liczbę wież, z których każda składa się z dokładnie $n$ cegiełek. Następnie Bajtek próbuje w jak najmniejszej liczbie ruchów zrównoważyć wagę. Jedyna czynność, jaką może wykonywać, to usunięcie cegiełki z wierzchołka dowolnej wieży.

Bajtkowi bardzo spodobała się ta gra, lecz zauważył, że nie potrafi stwierdzić, czy jego rozwiązanie składa się z minimalnej liczby ruchów. Napisz program, który wyznaczy najmniejszą liczbę ruchów umożliwiającą zrównoważenie wagi, by Bajtek mógł zweryfikować swoje umiejętności w wymyślonej przez siebie grze.

W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite $n$, $l$ oraz $p$ ($1 ≤ n ≤ 50$, $1 ≤ l, p ≤ 25$), pooddzielane pojedynczymi odstępami, oznaczające odpowiednio liczbę cegiełek, z których składa się każda wieża, liczbę wież na lewej szalce oraz liczbę wież na prawej szalce. W każdym z następnych $l$ wierszy znajduje się opis jednej spośród wież na lewej szalce. Każdy taki opis składa się z $n$ liczb całkowitych $w_{k,i}$ ($-50 ≤ w_{k,i} ≤ 50$) pooddzielanych pojedynczymi odstępami, oznaczających wagi kolejnych cegiełek -tej wieży, począwszy od jej spodu do wierzchołka. W kolejnych $p$ wierszach znajduje się opis wież na prawej szalce, w takim samym formacie.

W pierwszym i jedynym wierszu standardowego wyjścia Twój program powinien wypisać jedną liczbę całkowitą, oznaczającą minimalną liczbę ruchów potrzebnych do zrównoważenia wagi.

Wyjaśnienie do przykładu: Suma wag cegiełek na lewej szalce jest równa 8, a na prawej 9. Aby zrównoważyć szalki, Bajtek może zdjąć po jednej cegiełce z drugiej wieży na lewej szalce i z pierwszej wieży na prawej szalce; wówczas obciążenie szalek wyniesie $3 + 4 + (-1) = 6 = 7 + (-2) + 1$.