W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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.)
Napisz program, który:
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 .
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.
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.