Mapka w kratkę

Limit pamięci: 32 MB

Mapa Bajtocji, wraz z naniesionymi południkami i równoleżnikami, tworzy prostokąt o wymiarach ( to jego wysokość, a - szerokość). Równoleżniki są oznaczone na mapie poziomymi liniami, ponumerowanymi od do , zaś pionowe południki mają numery od do (patrz obrazek na drugiej stronie treści zadania).

Prognozowanie pogody w Bajtocji jest zadaniem niełatwym. Dla każdego obszaru jednostkowego (tj. leżącego pomiędzy sąsiednimi południkami i równoleżnikami) wiemy, jak długo bajtocki komputer meteorologiczny będzie obliczał prognozę. Uwarunkowania topograficzne powodują, że czas ten może być różny dla różnych obszarów. Dotychczas prognoza pogody przygotowywana była w najprostszy możliwy sposób: jeden komputer obliczał prognozę kolejno dla wszystkich obszarów jednostkowych. Obliczenie prognozy pogody dla całej Bajtocji zajmowało więc tyle czasu, ile wynosi suma wszystkich czasów obliczeń dla poszczególnych obszarów.

Zostałeś poproszony o opracowanie nowego systemu przeznaczonego na komputer wieloprocesorowy. Aby rozdzielić obliczenia pomiędzy procesory, teren Bajtocji należy podzielić, poprzez wybór równoleżników i południków, na mniejszych obszarów. Każdy z procesorów będzie obliczał pogodę dla jednego prostokąta z tego podziału, przetwarzając kolejno obszary jednostkowe. Wszystkie procesory pracować będą jednocześnie. Cała prognoza pogody będzie gotowa, gdy tylko ostatni procesor zakończy swoją pracę.

Twoim zadaniem jest wyznaczenie minimalnego możliwego czasu obliczenia całej prognozy pogody, odpowiadającego jakiemuś wyborowi równoleżników i południków.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia rozmiary mapy Bajtocji, liczbę południków i równoleżników oraz czasy liczenia prognozy pogody dla poszczególnych obszarów jednostkowych,
• wyznaczy minimalny czas potrzebny na obliczenie prognozy pogody,
• wypisze znaleziony wynik na standardowe wyjście.

Wejście

Pierwszy wiersz wejścia zawiera cztery liczby całkowite , , i , pooddzielane pojedynczymi odstępami (, ). Kolejne wierszy zawiera czasy liczenia prognozy pogody dla poszczególnych obszarów jednostkowych. -ta liczba w -szym wierszu reprezentuje - czas potrzebny do obliczenia prognozy pogody dla obszaru pomiędzy -szym a -tym równoleżnikiem oraz pomiędzy -szym a -tym południkiem (, , ).

Dodatkowo, w testach wartych sumarycznie 40% punktów, i nie przekroczą .

Wyjście

Twój program powinien wypisać dokładnie jeden wiersz zawierający jedną liczbą całkowitą - optymalny czas obliczenia prognozy pogody.

Przykład

Dla danych wejściowych:

7 8 2 1
0 0 2 6 1 1 0 0
1 4 4 4 4 4 3 0
2 4 4 4 4 4 3 0
1 4 4 4 8 4 4 0
0 3 4 4 4 4 4 3
0 1 1 3 4 4 3 0
0 0 0 1 2 1 2 0

poprawną odpowiedzią jest:

31

Drugi i czwarty równoleżnik oraz czwarty południk dzielą Bajtocję na 6 obszarów, dla których czasy liczenia prognozy pogody to: 21, 13, 27, 27, 17, 31. Czas liczenia całej prognozy to 31.

Autor zadania: Zbigniew Czech.