상자 쌓기

직육면체 모양의 창고에 상자를 차례대로 쌓으려고 한다. 창고의 높이는 충분히 높다고 가정한다.

각 상자는 입력에 주어진 순서대로 하나씩 들어오며, 놓아야 할 위치가 정확히 정해져 있다. 상자는 회전할 수 없고, 모든 모서리는 창고의 좌표축과 평행하다.

창고 바닥의 남서쪽 꼭짓점을 원점으로 잡는다. x축은 동쪽, y축은 북쪽, z축은 위쪽을 향한다. 상자의 바닥에서 가장 남서쪽인 꼭짓점의 좌표가 (px, py)가 되도록 놓는다. 상자를 놓을 때에는 그 상자의 바닥이 덮는 영역 아래에 이미 쌓인 부분 중 가장 높은 고도 위에 상자가 올라간다.

모든 상자를 순서대로 쌓은 뒤, 가장 높은 곳의 고도를 구하여라.

첫 줄에 세 정수 Lx, Ly, N이 주어진다. Lx와 Ly는 창고 바닥의 가로와 세로 길이이고, N은 들어오는 상자의 개수이다.

다음 N개의 줄에는 상자가 들어오는 순서대로 다섯 정수 lx, ly, lz, px, py가 주어진다. lx, ly, lz는 각각 상자의 가로, 세로, 높이이고, (px, py)는 상자 바닥의 남서쪽 꼭짓점이 놓일 좌표이다.

제한은 다음과 같다.

• 1 <= Lx, Ly <= 1,000
• 1 <= N <= 20,000
• 1 <= lx, 0 <= px, px + lx <= Lx
• 1 <= ly, 0 <= py, py + ly <= Ly
• 1 <= lz <= 100,000

모든 상자를 쌓은 뒤 가장 높은 곳의 고도를 첫 줄에 출력한다.

네 개의 상자를 순서대로 쌓은 뒤 각 상자의 꼭짓점 좌표는 다음과 같다.

• 첫 번째 상자: (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)