Waga

Limit pamięci: 16 MB

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 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.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite , oraz (, ), 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 wierszy znajduje się opis jednej spośród wież na lewej szalce. Każdy taki opis składa się z liczb całkowitych () pooddzielanych pojedynczymi odstępami, oznaczających wagi kolejnych cegiełek -tej wieży, począwszy od jej spodu do wierzchołka. W kolejnych wierszach znajduje się opis wież na prawej szalce, w takim samym formacie.

Wyjście

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.

Przykład

Dla danych wejściowych:

2 2 2
4 3
-1 2
7 3
1 -2

poprawną odpowiedzią jest:

2

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 .

Autorzy zadania: Joanna Bujnowska, Jacek Tomasiewicz.