Pyramid Base 2

You need the largest pyramid site your budget allows. A land survey divides the site into an $M \times N$ grid of square cells. The base of the pyramid must be a square with sides parallel to the grid.

The survey found $P$ obstacles. Each obstacle is a rectangle with sides parallel to the grid, and obstacles may overlap. To build the pyramid, every cell covered by its base must be cleared of obstacles. Removing obstacle $i$ costs $C_i$. An obstacle can only be removed whole, never in part. Removing one obstacle leaves any obstacle that overlaps it untouched.

Given the dimensions $M$ and $N$, the position and removal cost of each of the $P$ obstacles, and the budget $B$, write a program that finds the largest possible side length of the base such that the total removal cost does not exceed $B$.

The first line contains $M$ and $N$, separated by one space. ($1 \le M, N \le 10^6$)

The second line contains the budget $B$. ($0 < B \le 2 \times 10^9$)

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

Each of the next $P$ lines describes one obstacle. The $i$th of these lines describes obstacle $i$ and contains five integers $X_{i1}$, $Y_{i1}$, $X_{i2}$, $Y_{i2}$, $C_i$, separated by single spaces. The first two are the coordinates of the bottommost leftmost cell of the obstacle, the next two are the coordinates of the topmost rightmost cell, and the last 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 7000$)

Print one integer, the largest side length of the base that can be prepared. If no pyramid can be built at all, print $0$.

The figure shows two placements of a base with side length $4$.