Pyramid base#278
You are asked to find the largest possible base size for building a new pyramid. You are given a plan of the available land, which is divided into an M \times N grid of square cells. The base of the pyramid must be a square with sides parallel to the grid.
There are rectangular obstacles, each parallel to the grid sides. Obstacles can overlap. To build the pyramid, all cells covered by the base must be cleared of obstacles.
Removing the -th obstacle costs C_i. Each obstacle must be removed completely; you cannot remove only part of an obstacle. Removing one obstacle does not affect others.
Write a program that, given the grid dimensions and , descriptions of the obstacles, the cost to remove each obstacle, and a budget , finds the maximum possible side length of the pyramid's base such that the total obstacle removal cost does not exceed .
Your program will be graded on three disjoint test sets. For all, the following constraints apply:
The program reads the input in the following format:
- Line : Two integers and (1 \leq M, N \leq 1\ 000\ 000), the size of the grid. - Line : Integer , your budget. - Line : Integer , the number of obstacles. - Each of the next lines: X_{i1}\ Y_{i1}\ X_{i2}\ Y_{i2}\ C_i (1 \leq X_{i1} \leq X_{i2} \leq M, 1 \leq Y_{i1} \leq Y_{i2} \leq N), the coordinates of the bottom-left and top-right cells of the obstacle and its removal cost.
The bottom-left cell of the grid has coordinates ; the top-right cell has coordinates (M, N).
Print a single integer: the largest possible side length of the pyramid's base that can be prepared. If it is not possible to build the pyramid, print .
Example 1