Pyramid Base

Time limit5sMemory limit128 MB

Summary

Given up to 1000 weighted rectangles on a grid up to 10^6 by 10^6, find the largest axis-aligned square whose total cost of intersected rectangles is at most B.

Level: Hard8 of 10
Topics: Binary search, Geometry, Prefix sum, Implementation
Solved: No attempts yet

Problem

You want to find the largest affordable site for building a new pyramid. To help you decide, you are given a survey of the available land, conveniently divided into an $M \times N$ grid of square cells. The base of the pyramid must be a square whose sides are parallel to those of the grid.

The survey identified a set of $P$ possibly overlapping obstacles, each described as a rectangle in the grid with sides parallel to those of the grid. To build the pyramid, every cell covered by its base must be cleared of obstacles. Removing the $i$ -th obstacle costs $C_i$ . An obstacle must always be removed completely; you cannot remove only part of one. Also, removing an obstacle does not affect any other obstacle that overlaps it.

Given the survey dimensions $M$ and $N$ , the descriptions of the $P$ obstacles, the removal cost of each obstacle, and your budget $B$ , write a program that finds the maximum possible side length of the pyramid's base such that the total cost of removing obstacles does not exceed $B$ .

Input

Your program must read the following data from standard input.

Line 1: two integers $M$ and $N$ , separated by a single space. ( $1 \le M, N \le 10^{6}$ )
Line 2: the integer $B$ , the maximum cost you can afford (your budget). ( $B = 0$ )
Line 3: the integer $P$ , the number of obstacles found in the survey. ( $1 \le P \le 1000$ )
Each of the next $P$ lines describes one obstacle. The $i$ -th such line describes the $i$ -th obstacle and consists of five integers $X_{i1}$ , $Y_{i1}$ , $X_{i2}$ , $Y_{i2}$ , and $C_i$ , separated by single spaces. They give, respectively, the coordinates of the bottommost-leftmost cell of the obstacle, the coordinates of the topmost-rightmost cell of the obstacle, and the removal cost. 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$ )

Output

Your program must write a single line to standard output containing one integer: the maximum possible side length of the pyramid's base that can be prepared. If no pyramid can be built, output $0$ .

Hint

The figure shows the only possible location for a pyramid base with a side of length $3$ .

Examples2

Example 1

Input

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

Expected output

Example 2
Input
```
2 2
0
1
1 1 1 1 5
```
Expected output
```
1
```