시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 2 0 0 0.000%

문제

넓은 창고에 상자들을 쌓으려고 한다. 상자는 하나씩 창고에 입고되며, 입고되는 순서대로 쌓아 나가야 한다. 또, 각 상자마다 그 상자를 쌓아야 하는 위치가 정확히 지정되어 있으며, 쌓을 때 회전시킬 수도 없다. 상자들은 직육면체 모양으로, 가로, 세로, 높이의 길이가 다양하다. 상자를 쌓아 둘 창고 역시 직육면체 모양이지만, 그 높이는 충분히 높다고 가정하자.

편의상 창고 바닥의 남서쪽 코너를 원점으로 하여 좌표계를 구성하도록 한다. 창고의 각 모서리는 x, y, z 각 좌표축에 평행하거나 수직하다. x축은 동쪽 방향, y축은 북쪽 방향, z축은 하늘 방향으로 잡는다. 물론 상자들도 각 모서리가 x, y, z축에 평행하거나 수직하게 되도록 쌓을 것이다.

여러분이 할 일은, 주어진 순서대로 각 상자들을 쌓았을 때, 가장 높은 위치의 고도를 알아내는 것이다. 이를 위한 프로그램을 작성하라.

입력

첫 줄에 세 정수 Lx, Ly, N이 주어진다. (1≤Lx, Ly≤1,000. 1≤N≤20,000) Lx와 Ly는 창고의 가로, 세로 길이이며, N은 입고되는 상자의 개수이다. 이후 N개의 줄에 각 상자의 정보가 입고되는 순서로 주어진다. 이는 다섯 개의 정수 lx, ly, lz, px, py 로 이루어진다. (1≤lx, 0≤px, px+lx≤Lx, 1≤ly, 0≤py, py+ly≤Ly, 1≤lz≤100,000) lx, ly, lz는 각각 상자의 가로, 세로, 높이 길이를 나타낸다. px, py는 상자를 쌓아야 하는 위치를 나타낸다. 상자 바닥의 네 꼭지점 중 가장 남서쪽에 있는 것의 x, y좌표를 px, py에 맞추어 쌓으면 된다.

출력

첫 줄에 상자를 모두 쌓았을 때, 가장 높은 곳의 고도를 출력한다.

예제 입력

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

예제 출력

6

힌트

네 개의 상자를 순서대로 모두 쌓고 난 뒤, 각 상자의 꼭지점 좌표는 다음과 같다.
첫 번째 상자 : (0,0,0), (4,0,0), (4,3,0), (0,3,0), (0,0,2), (4,0,2), (4,3,2), (0,3,2)
두 번째 상자 : (3,0,2), (6,0,2), (6,3,2), (3,3,2), (3,0,3), (6,0,3), (6,3,3), (3,3,3)
세 번째 상자 :(0,3,0), (7,3,0), (7,4,0), (0,4,0), (0,3,2), (7,3,2), (7,4,2), (0,4,2)
네 번째 상자 : (2,2,3), (4,2,3), (4,5,3), (2,5,3), (2,2,6), (4,2,6), (4,5,6), (2,5,6)