Stacking Boxes

You want to stack boxes in a rectangular warehouse. The warehouse is assumed to be tall enough.

The boxes arrive one by one in the order given by the input. Each box has a fixed position, cannot be rotated, and all of its edges are parallel to the coordinate axes of the warehouse.

Use the southwestern corner of the warehouse floor as the origin. The x axis points east, the y axis points north, and the z axis points upward. A box is placed so that the southwestern corner of its bottom face is at (px, py). When a box is placed, its bottom rests on the highest existing height under any part of its footprint.

After all boxes have been stacked in order, find the highest altitude reached anywhere.

The first line contains three integers Lx, Ly, and N. Lx and Ly are the width and depth of the warehouse floor, and N is the number of boxes.

Each of the next N lines contains five integers lx, ly, lz, px, and py, in arrival order. lx, ly, and lz are the width, depth, and height of the box. (px, py) is the coordinate of the southwestern corner of the box's bottom face.

The constraints are:

• 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

Print the highest altitude after all boxes have been stacked.

After the four boxes are stacked in order, the vertices of each box are as follows.

• First box: (0,0,0), (4,0,0), (4,3,0), (0,3,0), (0,0,2), (4,0,2), (4,3,2), (0,3,2)
• Second box: (3,0,2), (6,0,2), (6,3,2), (3,3,2), (3,0,3), (6,0,3), (6,3,3), (3,3,3)
• Third box: (0,3,0), (7,3,0), (7,4,0), (0,4,0), (0,3,2), (7,3,2), (7,4,2), (0,4,2)
• Fourth box: (2,2,3), (4,2,3), (4,5,3), (2,5,3), (2,2,6), (4,2,6), (4,5,6), (2,5,6)