Problem Description

You need to find the largest possible area within your financial means to build a new pyramid. To assist you in making this decision, a land survey map is provided. For convenience, the land is divided into a grid of $M \times N$ small squares. The base of the pyramid must be a square with its sides parallel to the grid lines.

The survey map marks $P$ potentially overlapping obstacles, which are rectangular areas on the grid with their sides parallel to the grid lines. To build the pyramid, any obstacles within the squares occupied by the pyramid base must be removed. Removing obstacle $i$ incurs a cost of $C_i$. When removing an obstacle, it must be removed in its entirety; partial removal is not allowed. Additionally, removing an obstacle has no effect on other overlapping obstacles.

Given the dimensions $M$ and $N$ of the grid, descriptions of the $P$ obstacles, the removal costs for each obstacle, and your budget $B$, write a program to determine the maximum side length of the pyramid base such that the total cost of removing obstacles does not exceed $B$.

Input Format

Your program should read the following data from standard input:
- The first line contains two integers separated by a single space, representing $M$ and $N$.
- The second line contains an integer $B$, which is your maximum allowable cost (your budget).
- The third line contains an integer $P$, the number of obstacles marked on the survey map.
- The next $P$ lines each describe an obstacle. The $i$-th line contains five integers separated by a single space: $X_{i1}, Y_{i1}, X_{i2}, Y_{i2}$, and $C_i$, representing the coordinates of the bottom-left and top-right squares of the obstacle, and the cost to remove this obstacle, respectively. The bottom-left square of the grid has coordinates $(1,1)$, and the top-right square has coordinates $(M, N)$.

Output Format

Your program must output a single line to standard output containing a single integer, which is the maximum side length of the pyramid base. If no pyramid can be built, the program should output 0.

Sample Input and Output

Sample Input #1

6 9
42
5
4 1 6 3 12
3 6 5 6 9
1 3 3 8 24
3 8 6 9 21
5 1 6 2 20

Sample Output #1

4

Sample Input #2

13 5
0
8
8 4 10 4 1
4 3 4 4 1
10 2 12 2 2
8 2 8 4 3
2 4 6 4 5
10 3 10 4 8
12 3 12 4 13
2 2 4 2 21

Sample Output #2

3

Notes/Hints

Data Range

The program is evaluated using three disjoint sets of data. The following constraints apply to all test data:
- $1 \leq M, N \leq 1,000,000$ for the grid dimensions.
- $1 \leq C_i \leq 7,000$ for the cost to remove obstacle $i$.
- For each obstacle $i$, $1 \leq X_{i1} \leq X_{i2} \leq M$ and $1 \leq Y_{i1} \leq Y_{i2} \leq N$.

The first set of tests is worth 35 points:
- $B = 0$ — the maximum allowable cost (no obstacles can be removed).
- $1 \leq P \leq 1,000$ — the number of obstacles in the grid.

The second set of tests is worth 35 points:
- $0 < B \leq 2,000,000,000$ — your budget.
- $1 \leq P \leq 30,000$ — the number of obstacles in the grid.

The third set of tests is worth 30 points:
- $B = 0$ — your budget (no obstacles can be removed).
- $1 \leq P \leq 400,000$ — the number of obstacles in the grid.

见题面 Input 部分

见题面 Output 部分