Programacion Competitiva Bolivia

Tras haber vivido 3 años en la misma casa, Rafael decidió que ha llegado la hora de mudarse a una casa nueva en el barrio más prestigioso de la ciudad. Después de encontrar una casa a un precio realmente bueno, Rafael quiere empezar por cambiar todo el suelo de madera (excepto algunas habitaciones como el cuarto de baño o la cocina) por una moqueta, para no pasar tanto frío.

Así que Rafael fue al Centro Internacional de Interiores de Casas (CIIC). Allí se encontró con una sorpresa: sólo se vendían porciones cuadradas de moqueta con tamaños enteros (en metros), todos ellos vendidos al mismo precio, sin importar el tamaño. El CIIC se ofrece para colocar la moqueta siempre y cuando se respeten las siguientes condiciones:

• Las porciones de moqueta no se pueden cortar;
• Todos los lugares de la casa, excepto las habitaciones específicamente marcadas para no tener moqueta, deben quedar cubiertas exactamente por una porción de moqueta;
• Ninguna porción de moqueta puede salir fuera de casa.

El CIIC sólo se dedica a la colocación de la moqueta, y es el cliente el que tiene que decidir qué porciones comprar y donde colocarlas. Podemos considerar que la casa nueva es un rectángulo donde la longitud y anchura son números enteros (en metros). Las habitaciones en las que no se debe poner moqueta también se pueden pensar como rectángulos, más pequeños, de longitud y anchura enteros.

La figura siguiente ilustra una casa de 7x6 metros, y dos habitaciones que no deben contener moqueta; una en la parte superior de 3x1 metros, y otra en la parte inferior de 3x2 metros. Si el coste de cada porción fuera de 25 euros, una posible forma de minimizar el precio consistiría en colocar una porción de 4x4, una porción de 3x3, y dos porciones de 2x2 de la forma que se muestra. En total, haría falta comprar 4 porciones, con un coste final de 100 euros.

Rafael necesita ayuda para descubrir cual es la solución más económica, es decir, la que minimiza la cantidad de dinero necesaria para renovar el suelo de su casa.

Dadas las dimensiones enteras de la casa nueva, N y M, representando su longitud y anchura, un conjunto de D habitaciones rectangulares indicando áreas donde no se debe colocar moqueta, y el precio P de cada porción cuadrada de moqueta (independientemente de su tamaño), hay que descubrir cual es la menor cantidad de dinero que hay que gastar para enmoquetar la casa como se describió anteriormente. Sólo se pueden usar porciones cuadradas, que no se pueden cortar, y toda la casa (excepto las habitaciones indicadas) deben quedar cubiertas de exactamente una porción de moqueta.

Input

La primera línea de la entrada contiene dos enteros N y M, separados por un único espacio, indicando que la casa mide NxM metros.

A continuación viene una línea con el número D de habitaciones que no deben quedar cubiertas de moqueta. Después vienen exactamente D líneas describiendo estas habitaciones, cada una de ellas formada por cuatro enteros X1_i Y1_i X2_i Y2_i, indicando que existe una habitación cuyas esquinas están en las casillas (X1_i,Y1_i) y (X2_i,Y2_i). La casilla inferior izquierda es la (1, 1). Las habitaciones siempre están completamente contenidas dentro de la casa y no se solapan. También se garantiza que siempre hay una parte de la casa que debe ser cubierta de moqueta.

La última línea contiene un entero P, el precio de cada porción cuadrada de moqueta.

Se garantizan los límites siguientes en todos los casos de prueba:

Output

La salida debe contener una sola línea con el precio mínimo total que se debe pagar para enmoquetar toda la casa, tal y como se explicó anteriormente.

Example

Input:
7 6
2
5 1 7 2
5 6 7 6
25
Output: 100

Input 2:

5 5
3
1 2 2 5
1 1 1 1
3 1 5 2
100
Salida 2:

200
Explicación: El ejemplo 1 se corresponde con la figura mostrada anteriormente en el enunciado. El ejemplo 2 se corresponde con la figura siguiente: