\includegraphics{https://static.e-olymp.com/content/e3/e390003da5a9fb3cf824dbf8a8e4480434029106.jpg} Вас попросили отыскать размер наибольшего из возможных мест для строительства новой пирамиды. Для того, чтобы помочь вам принять решение, вам предоставлен план доступного участка, который для удобства поделен сеткой на \textbf{MxN} квадратных клеток. Основание пирамиды должно быть квадратом со сторонами, параллельными сторонам сетки. На плане показано множество из \textbf{P} препятствий, которые являются прямоугольниками со сторонами, параллельными сторонам сетки. Прямоугольники могут перекрываться. Чтобы построить пирамиду, все клетки, покрытые ее основанием, должны быть очищены от препятствий. Устранение \textbf{i}-го препятствия имеет стоимость \textbf{C_i}. Всякий раз, когда препятствие устраняется, оно устраняется полностью, то есть, вы не можете устранить только часть препятствия. Следует заметить, что устранение препятствия не влияет на другие препятствия, с которыми оно перекрывалось. Напишите программу, которая по заданным размерностям сетки \textbf{M} и \textbf{N}, описанию \textbf{P} препятствий, стоимости устранения каждого из них, а также имеющемуся бюджету \textbf{B} находит максимальную длину стороны наибольшего из возможных мест для основания пирамиды, такого, что суммарная стоимость устранения препятствий не превосходит \textbf{B}. \textbf{Ограничения} Ваша программа будет оценена с использованием трех непересекающихся наборов тестов. Для всех них выполняются следующие ограничения: \textbf{1 <= M, N <= 1 000 000} (\textbf{M}, \textbf{N} -- размерности решетки) \textbf{1 <= C_i <= 7 000} (\textbf{C_i} -- стоимость устранения \textbf{i}-го препятствия) \textbf{1 <= X_i1 <= X_i2 <= M} (\textbf{X_i1} и \textbf{X_i2} -- \textbf{X}-координаты самой левой и самой правой клетки \textbf{i}-го препятствия, соответственно) \textbf{1 <= Y_i1 <= Y_i2 <= N} (\textbf{Y_i1} и \textbf{Y_i2} -- \textbf{Y}-координаты самой нижней и самой верхней клетки \textbf{i}-го препятствия, соответственно) \InputFile Ваша программа должна читать из стандартного ввода данные в следующем формате: • Строка \textbf{1} содержит два целых числа, разделенных одним пробелом -- \textbf{M} и \textbf{N}, соответственно. • Строка \textbf{2} содержит целое число \textbf{B} -- ваш бюджет. • Строка \textbf{3} содержит целое число \textbf{P} -- количество препятствий, имеющихся на плане. • Каждая из последующих \textbf{P} строк описывает препятствие: \textbf{i}-ая из этих строк описывает \textbf{i}-ое препятствие. Каждая строка состоит из \textbf{5} целых чисел: \textbf{X_i1}, \textbf{Y_i1}, \textbf{X_i2}, \textbf{Y_i2}, и \textbf{C_i}, разделенных одиночными пробелами. Они задают соответственно координаты нижней левой клетки препятствия, координаты верхней правой клетки препятствия и стоимость устранения препятствия. Нижняя левая клетка решетки имеет координаты (\textbf{1}, \textbf{1}), верхняя правая клетка решетки имеет координаты (\textbf{M}, \textbf{N}). \OutputFile Ваша программа должна вывести в стандартный вывод единственную строку, содержащую одно целое число -- максимальную возможную длину стороны основания пирамиды, которую можно построить. Если пирамиду построить нельзя, ваша программа должна вывести число \textbf{0}.