Autobus
Limit pamięci: 32 MB
Ulice Bajtogrodu tworzą szachownicę -
prowadzą z północy na południe, lub ze wschodu na zachód.
Ponadto każda ulica prowadzi na przestrzał przez całe miasto -
każda ulica biegnąca z północy na południe krzyżuje się z każdą ulicą
biegnącą ze wschodu na zachód i vice versa.
Ulice prowadzące z północy na południe są ponumerowane od do ,
w kolejności z zachodu na wschód.
Ulice prowadzące ze wschód na zachód są ponumerowane od do ,
w kolejności z południa na północ.
Każde skrzyżowanie -tej ulicy biegnącej z północy na południe i
-tej ulicy biegnącej ze wschodu na zachód oznaczamy parą liczb
(dla ).
Po ulicach Bajtogrodu kursuje autobus.
Zaczyna on trasę przy skrzyżowaniu , a kończy przy
skrzyżowaniu .
Ponadto autobus może jechać ulicami tylko w kierunku wschodnim
i/lub północnym.
Przy pewnych skrzyżowaniach oczekują na autobus pasażerowie.
Kierowca autobusu chce tak wybrać trasę przejazdu autobusu, aby
zabrać jak najwięcej pasażerów.
(Zakładamy, że bez względu na wybór trasy i tak wszyscy
pasażerowie zmieszczą się w autobusie.)
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia opis siatki ulic oraz liczbę
pasażerów czekających przy poszczególnych skrzyżowaniach,
-
obliczy ilu maksymalnie pasażerów może zabrać autobus,
-
wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu pliku wejściowego zapisane są trzy dodatnie
liczby całkowite , i - odpowiednio: liczba ulic
biegnących z północy na południe, liczba ulic biegnących ze
wschodu na zachód i liczba skrzyżowań, przy których
pasażerowie czekają na autobus
(, , ).
Kolejne wierszy opisuje rozmieszczenie pasażerów czekających
na autobus, w jednym wierszu opisani są pasażerowie czekający
na jednym ze skrzyżowań.
W wierszu znajdują się trzy dodatnie liczby całkowite
i , oddzielone pojedynczymi odstępami,
, , .
Taka trójka liczb oznacza, że przy skrzyżowaniu
oczekuje pasażerów.
Każde skrzyżowanie pojawia się w danych wejściowych co najwyżej
raz.
Łączna liczba oczekujących pasażerów nie przekracza
.
Wyjście
Twój program powinien na wyjściu wypisać jeden wiersz
zawierający jedną liczbę całkowitą - maksymalną liczbę
pasażerów, których może zabrać autobus.
Przykład
Dla danych wejściowych:
8 7 11
4 3 4
6 2 4
2 3 2
5 6 1
2 5 2
1 5 5
2 1 1
3 1 1
7 7 1
7 4 2
8 6 2
poprawną odpowiedzią jest:
11
W tym przypadku Twój program powinien podać wynik 11.
Na poniższym rysunku zaznaczono skrzyżowania przez które przejedzie autobus
zabierając 11 pasażerów.
Autor zadania: Wojciech Rytter.