Международные олимпиады: IOI - 2008

Подстрочный перевод

Вас просят найти наибольшее подходящее пространство для постройки новой пирамиды. Вам предоставлена информация о доступной для застройки земли в виде квадратной сетки размера N на M. Основание пирамиды должно быть квадратом со сторонами, параллельными линиям этой сетки и с вершинами, лежащими в узлах этой сетки.

Исследование обнаружило множество из P возможно пересекающихся препятствий, каждое из которых описано прямоугольником на сетке. Для того, чтобы построить пирамиду, все клетки, содержащиеся в квадрате её основания, должны быть расчищены от препятствий. Удаление i-го препятствия стоит C_i, препятствия удаляются целиком. Удаление препятствия не оказывает влияния на другие препятствия, даже пересекающиеся.

Напишите программу, которая по описанию земли для застройки, описанию препятствий и стоимости их удаления и по количеству денег B, которое можно потратить на удаление препятствий, определяет максимально возможную длину стороны основания пирамиды, которую можно построить после очистки земли.

Ограничения

Тесты к этой задаче разбиты на три группы. Для всех групп тестов выполняются следующие ограничения:

Размеры сетки:
1 <= M, N <= 1,000,000
Стоимости удаления препятствий:
1 <= Ci <= 7,000
X-координаты самых левых и самых правых клеток препятствий:
1 <= Xi,1 <= Xi,2 <= M
Y-координаты самых верхних и самых нижний клеток препятствий:
1 <= Yi,1 <= Yi,2 <= N

Количество денег:
B = 0
Количество препятствий:
1 <= P <= 1,000

Количество денег:
0 < B < 2,000,000,000
Количество препятствий:
1 <= P <= 30,000

Количество денег:
B = 0
Количество препятствий:
1 <= P <= 400,000

Формат входных данных

В первой строке два числа -- M и N соответственно.
Во второй строке одно число B.
В третьей строке одно число P.
Каждая из следующих P строк содержит в себе описание очередного препятствия -- пять чисел X_i,1, Y_i,1, X_i,2, Y_i,2, и C_i.

Формат выходных данных

Выведите одно число - максимально возможную длину стороны основания пирамиды. Если никакую пирамиду построить невозможно, то выведите число 0.

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

4

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

3