Un adinerado comerciante de los azucareros del centro ha ideado una manera de ahorrar en los impuestos de carretera que sus camiones pagan al circular por las autopistas del estado. El plan consiste en comprar aquellas partes de la autopista que son más rentables. De esa manera los camiones cuyas rutas pasen completamente por sus propiedades no tienen que pagar impuesto.

La autopista está dividida en secciones con longitud de un kilómetro. ~{[0,1], [1,2], [10,9]}~ son ejemplos de secciones de la autopista, siendo estas las secciones ~1~,~2~ y ~10~ respectivamente. Para cada kilómetro de la autopista sabemos su precio de venta. Para determinar cuáles secciones él quiere comprar, el comerciante revisará el plan de viajes para el próximo año. El conoce todas las rutas por las que sus camiones viajarán. Cada ruta está determinada por tres números ~A, B~ y ~C~ de la siguiente manera:

• El camión entrará en la autopista ~A~ kilómetros desde el comienzo de la autopista y dejará la autopista ~B~ kilómetros desde el comienzo, así viajando ~|B-A|~ kilómetros en la autopista. Por ejemplo, si el camión necesita viajar ~L~ kilómetros desde el comienzo de la autopista, ~A=0~ y ~B=L~.

• Si la ruta completa desde ~A~ hasta ~B~ es propiedad del comerciante, el camión no pagará impuesto.

• De lo contrario, si el camión tiene que pasar a través de al menos una sección que no es propiedad del comerciante, el tendrá que pagar un total de ~C~ (sin tener en cuenta el número de secciones de la autopista propiedad del estado por las que el camión tiene que pasar).

Adicionalmente el estado ha puesto una ley: en cada sección de la autopista propiedad del estado, a lo sumo ~K~ camiones pueden pasar en una dirección y ~K~ en otra dirección.

Escriba un programa que calcule el mínimo gasto total para el comerciante, de tal manera que todos sus camiones puedan completar sus rutas. El gasto total es definido como el gasto por comprar algunas partes de la autopista más todos los impuestos pagados por cada camión circulando por una ruta que no es propiedad del comerciante.

Entrada

En la primera línea de la entrada usted puede leer ~L (1 \le L \le 10^5)~, la longitud total de la autopista en kilómetros.

En la segunda línea hay L enteros ~X_i (0 \le X_i \le 10^9)~, el precio de compra de la i-ésima sección de la autopista.

La tercera línea contiene a ~N (1 \le N \le 10^5)~, el número de rutas que los camiones tomarán.

En cada una de las siguientes N líneas hay tres enteros ~A_i, B_i~ y ~C_i~ ~(0 \le A_i, B_i \le L, A_i \neq B_i, 0 \le C_i \le 10^9)~, la descripción de la i-ésima ruta.

La última línea contiene al número ~K (1 \le K \le 100)~, el número máximo de camiones que pueden ir en cada dirección en la sección de la autopista propiedad del estado.

Salida

En la salida aparecerá solamente un entero, el cual representa al gasto total mínimo para el comerciante si el selecciona óptimamente y compra algunas secciones de la autopista.

Ejemplo #1 de Entrada

3 
300 300 300 
2 
0 3 400 
2 1 400 
99

Ejemplo #1 de Salida

700

Ejemplo #2 de Entrada

10 
1 3 3 1 1 1 2 2 2 3 
5 
0 10 2 
1 5 4 
1 4 4 
9 0 2 
10 9 4 
2

Ejemplo #2 de Salida

15

Descripción del ejemplo #1:

Cada una de las secciones {[0,1]; [1,2]; [2,3]} vale 300.

Si el comerciante no compra alguna sección, él tiene que pagar un total de 800 (400 de impuesto por cada ruta). Si el compra la autopista completa, el pagará 900. Pero si el compra solamente la segunda sección el pagará 300 por esta más 400 por el impuesto de la primera ruta (la segunda ruta va solamente a través de la segunda sección).