Largest Pyramid Base

You are given a land survey of an area divided into a grid of size M × N (rows × columns). You plan to build a pyramid and need to select the largest possible square area (with its sides parallel to the grid) as the foundation. However, there are P obstacles marked on the survey. Each obstacle is an axis‐aligned rectangle (possibly overlapping with others) given by its top‐left and bottom‐right coordinates and has a removal cost. When building the pyramid, if the chosen square overlaps any obstacle, you must entirely remove that obstacle (even if only part of it falls inside the square). The total removal cost must not exceed your budget B.

Formally, the grid is divided into M × N unit squares. There are P obstacles; the i-th obstacle is described by five integers: r₁, c₁, r₂, c₂, C_i, which indicates that the obstacle covers all cells from row r₁ to row r₂ and column c₁ to column c₂ (inclusive). If the foundation square (of side length L) is placed with its top‐left corner at cell (i, j), then it covers rows i to i+L-1 and columns j to j+L-1. For each obstacle that intersects the square (i.e. their regions have nonempty intersection), you must pay its removal cost. Your task is to choose a placement and size for the pyramid’s base such that the total removal cost is at most B and the side length is maximized. If no valid square can be found, output 0.

The constraint for removing obstacles is that you must remove an entire obstacle if any part of it lies within the chosen square. Removal of one obstacle does not affect the others, even if they overlap.

Note: If a square does not intersect an obstacle at all, you do not need to remove it.

inputFormat

The first line contains four integers M, N, P, and B, representing the number of rows, the number of columns, the number of obstacles, and the budget, respectively.

Each of the next P lines contains five integers: r₁ c₁ r₂ c₂ C, where (r₁, c₁) is the top‐left coordinate and (r₂, c₂) is the bottom‐right coordinate of an obstacle, and C is the cost to remove that obstacle. All indices are 1-indexed and the sides of the obstacles are parallel to the grid.

outputFormat

Output a single integer: the maximum side length of the pyramid's base (i.e. the square) that can be cleared by removing obstacles with a total removal cost not exceeding B. If no such square exists, output 0.

sample

5 5 1 3
2 2 4 4 3

5