Se te pidió encontrar la ubicación mas grande costeable para construir una nueva pirámide. Para ayudarte a decidir, te han proporcionado una descripción del suelo disponible que ha sido convenientemente dividida en una cuadrículagrilla de ~M~ por ~N~ celdas cuadradas. La base de la pirámide debe de ser un cuadrado con lados paralelos a los de la cuadrículagrilla.

La descripción identificó un conjunto de ~P~ obstáculos (que posiblemente se traslapansolapan), que son descritos como rectángulos en la cuadrículagrilla con lados paralelos a los de la cuadrículagrilla. Para construir la pirámide, todas las celdas cubiertas por su base deben ser limpiadas de cualquier obstáculo. Quitar el i-ésimo obstáculo tiene un costo ~Ci~. En cualquier lugar que un obstáculo sea quitado, debe de ser quitado completamente, es decir, no puedes quitar solamente una parte de un obstáculo. También debes notar que quitar un obstáculo no afecta a otros obstáculos que lo traslapen

Tarea

Escribe un programa que, dados los tamaños ~M~ y ~N~ de la cuadrícula, la descripción de los ~P~ obstáculos, los costos de quitar cada uno de ellos y tu presupuesto ~B~, encuentre la longitud del lado de la base de la pirámide más grande posible tal que el costo total de quitar todos los obstáculos no exceda a ~B~.

Entrada

Tu programa deberá leer de entrada estándar los siguientes datos:

• La línea 1 contendrácontiene dos enteros separados por un espacio representando ~M~ y ~N~ respectivamente.
• La línea 2 contendrácontiene el entero ~B~, el máximo costo que puedes afrontar (tu presupuesto).
• La línea 3 contendrácontiene el entero ~P~, el número de obstáculos que se encuentran en la descripción.
• Cada una de las siguientes ~P~ líneas describen un obstáculo. La i-ésima de estas líneas describe el obstáculo ~i~. Cada línea consiste de ~5~ enteros: ~Xi1, Yi1, Xi2, Yi2,~ y ~Ci~ separados por espacios. Representando respectivamente las coordenadas de la celda de la esquina inferior izquierda del obstáculo, las coordenadas de la celda de la esquina superior derecha del obstáculo, y el costo de quitar el obstáculo. La celda de la esquina inferior izquierda de la cuadrícula tiene las coordenadas ~(1, 1)~ y la de la esquina superior derecha tiene las coordenadas ~(M, N)~.

Salida

Tu programa deberá escribir en la salida estándar una sola línea conteniendo un entero, el tamaño máximo posible de la longitud del lado de la base de la pirámide que puede ser construida. Si no es posible construir ninguna pirámide, tu programa deberá imprimir el número ~0~.

Restricciones

Tu programa será evaluado con tres conjuntos disjuntos de pruebas. Para todos ellos se cumplen las siguientes consideraciones:

~1 <= M, N <= 1,000,000~ Las longitudes de los lados de la cuadrículagrilla.

~1 <= Ci <= 7,000~ El costo de quitar el i-ésimo obstáculo.

~1 <= Xi1 <= Xi2 <= M~ Las coordenadas X de la celda superior izquierda y de la celda inferior derecha del i-ésimo obstáculo.

~1 <= Yi1 <= Yi2 <= N~ Las coordenadas Y de la celda superior izquierda y de la celda inferior derecha del i-ésimo obstáculo.

Para el primer conjunto de pruebas, que tendrá un valor de 35 puntos:

~B = 0~ El presupuesto que tienes.(No puedes quitar obstáculos)

~1 <= P <= 1,000~ El número de obstáculos en la cuadrícula.

Para el segundo conjunto de pruebas, que tendrá un valor de 35 puntos:

~0 < B <= 2,000,000,000~ El número de obstáculos en la cuadrícula

~1 <= P <= 30,000~ El número de obstáculos en la cuadrícula.

Para el tercer conjunto de pruebas, con un valor de 30 puntos:

~B = 0~. El presupuesto que tienes.(No puedes quitar obstáculos)

~1 <= P <= 400,000~. El número de obstáculos en la cuadrícula.

Ejemplo de Entrada #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

Ejemplo de Salida #1

4

La figura muestra dos posibles ubicaciones para la base de la pirámide, ambas tienen un lado con longitud 4

Ejemplo de Entrada #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

Ejemplo de Salida #2

3

La figura muestra la única ubicación posible para la base de la pirámide con lado de longitud 3.