Problem description

Autorzy gry Tetris postanowili stworzyć nową, trójwymiarową wersję gry, w której prostopadłościenne klocki będą opadać na prostokątną platformę. Podobnie jak w przypadku zwykłej, dwuwymiarowej wersji gry, klocki mają opadać osobno, w pewnej ustalonej kolejności. Dany klocek opada, dopóki nie natrafi na przeszkodę w postaci platformy albo innego, już stojącego klocka, a wtedy się zatrzymuje (w pozycji, w jakiej opadał) i pozostaje na swoim miejscu do końca gry.

Autorzy nowej gry postanowili jednak zmienić charakter gry, ze zręcznościowej na grę logiczną. Znając kolejność opadania klocków na płaszczyznę i tory ich lotu, gracz będzie musiał podać wysokość najwyżej położonego punktu w układzie powstałym po opadnięciu wszystkich klocków. Wszystkie klocki opadają pionowo w dół i nie obracają się w trakcie opadania. Dla ułatwienia wprowadźmy na platformie układ współrzędnych kartezjańskich o początku w jednym z jej narożników i osiach równoległych do jej boków.

Napisz program, który zautomatyzuje sprawdzanie, czy gracz udzielił poprawnej odpowiedzi.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opisy kolejno opadających klocków,
• wyznaczy najwyższy punkt układu klocków po zakończeniu ich opadania,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby całkowite D, S i N (1 ≤ N ≤ 20 000, 1 ≤ S, D ≤ 1 000), oddzielone pojedynczymi odstępami i oznaczające odpowiednio: długość i szerokość platformy oraz liczbę klocków, które na nią opadną. W następnych N wierszach występują opisy kolejnych klocków, po jednym w wierszu.

Każdy opis klocka składa się z pięciu liczb całkowitych: d, s, w, x oraz y (1 ≤ d, s ≤ D, d + x ≤ D, 1 ≤ s ≤ S, 0 ≤ y, s + y ≤ S, 1 ≤ w ≤ 100 000), reprezentujących klocek o długości d, szerokości s i wysokości w. Klocek ten będzie opadał na platformę ścianą o wymiarach d × s, przy czym długość i szerokość klocka będą równoległe odpowiednio do długości i szerokości platformy. Wierzchołki rzutu klocka na platformę będą miały współrzędne: (x,y), (x+d,y), (x,y+s) i (x+d,y+s).

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać dokładnie jedną liczbę całkowitą, oznaczającą wysokość najwyższego punktu w układzie klocków po zakończeniu ich opadania.

Przykład

7 5 4
4 3 2 0 0
3 3 1 3 0
7 1 2 0 3
2 3 3 2 2

6