Pyramid Base

You are looking for the largest site where the base of a new pyramid can stand. A survey has divided the available land into a grid of $M$ columns and $N$ rows of square cells. The base of the pyramid is a square, and its sides must be parallel to the sides of the grid.

The survey found $P$ obstacles, which may overlap each other. Every obstacle is a rectangle whose sides are parallel to the sides of the grid. To build the pyramid, no obstacle may remain on any cell that the base covers. Removing obstacle $i$ costs $C_i$, and an obstacle is always removed as a whole. You cannot remove only part of an obstacle. Removing one obstacle leaves every obstacle that overlaps it in place.

You are given the grid size $M$ and $N$, the position and the removal cost of each of the $P$ obstacles, and the budget $B$. Write a program that finds the largest side length of a base you can prepare while the total removal cost stays within $B$.

The first line contains $M$ and $N$, separated by a single space. ($1 \le M, N \le 1\,000\,000$)

The second line contains the budget $B$. In this problem $B$ is always $0$.

The third line contains $P$, the number of obstacles. ($1 \le P \le 400\,000$)

Each of the next $P$ lines describes one obstacle. The $i$th of those lines contains five integers $X_{i1}$, $Y_{i1}$, $X_{i2}$, $Y_{i2}$, $C_i$, separated by single spaces. The first four are the coordinates of the bottommost leftmost cell and of the topmost rightmost cell of obstacle $i$, and $C_i$ is the cost of removing that obstacle. The bottommost leftmost cell of the grid has coordinates $(1, 1)$, and the topmost rightmost cell has coordinates $(M, N)$. ($1 \le X_{i1} \le X_{i2} \le M$, $1 \le Y_{i1} \le Y_{i2} \le N$, $1 \le C_i \le 7\,000$)

On the first line, print the largest side length of a pyramid base you can prepare. If no pyramid can be built at all, print $0$.

The figure shows the layout of the example. The square drawn there is the only place where a base of side length $3$ fits.