N es el encargado de un almacén de verduras y se ocupa de diseñar su plan de ventas.
El almacén contiene $n$ tipos de verduras. N debe tener en cuenta las características de cada tipo y diversos factores para diseñar un plan de ventas razonable que maximice los ingresos.
Por cada unidad vendida de la verdura de tipo $i$, se obtienen unos ingresos de $a_i$.
En particular, como las políticas fomentan que los comerciantes diversifiquen sus ventas, la primera vez que se vende una verdura de tipo $i$ se reciben además unos ingresos adicionales de $s_i$.
Al comienzo de la actividad hay $c_i$ unidades de la verdura de tipo $i$ en existencias.
Sin embargo, las verduras se conservan durante un tiempo muy limitado y, una vez estropeadas, no pueden venderse. El ingenioso N ya ha calculado cuándo se estropea cada unidad: para la verdura de tipo $i$ existe un valor de conservación $x_i$, y al final de cada día se estropean $x_i$ unidades, hasta que se hayan estropeado todas. (Atención: el momento en que se estropea cada unidad está fijado y no cambia con las ventas).
Formalmente, para todo entero positivo $d$ que cumpla $d\times x_i\leq c_i$, hay $x_i$ unidades que se estropean al final del día $d$.
En particular, si $(d-1)\times x_i\leq c_i<d\times x_i$, hay $c_i-(d-1)\times x_i$ unidades que se estropean al final del día $d$.
Observa que $x_i=0$ significa que este tipo de verdura no se estropea.
Además, la cantidad total de verduras vendidas cada día está limitada a un máximo de $m$ unidades.
Ahora N tiene $k$ preguntas y quiere que le ayudes a calcular sus respuestas. Cada pregunta tiene la siguiente forma: dado $p_j$, si se venden verduras durante $p_j$ días, ¿cuáles son los máximos ingresos que se pueden obtener?
Entrada
Los datos se leen del archivo vegetables.in.
La primera línea contiene tres enteros positivos $n,m,k$, que representan, respectivamente, el número de tipos de verduras, el límite diario de unidades vendidas en total y el número de preguntas de N.
Cada una de las siguientes $n$ líneas contiene cuatro enteros no negativos que describen un tipo de verdura: $a_i,s_i,c_i,x_i$, en este orden, con los significados indicados anteriormente.
Cada una de las siguientes $k$ líneas contiene un entero no negativo $p_j$, con el significado indicado anteriormente.
Salida
La salida se escribe en el archivo vegetables.out.
Imprime $k$ líneas, cada una con un entero. El número de la línea $i$ es la respuesta a la pregunta $i$.
Ejemplos
Entrada 1
2 3 2 3 3 3 3 2 5 8 3 1 3
Salida 1
16 27
Ejemplo 2
Consulta vegetables/vegetables2.in y vegetables/vegetables2.ans en el directorio del concursante.
Ejemplo 3
Consulta vegetables/vegetables3.in y vegetables/vegetables3.ans en el directorio del concursante.
Nota del ejemplo 1
Hay dos tipos de verduras:
Al vender la verdura de tipo $1$, cada unidad proporciona unos ingresos de $3$ y su primera venta proporciona unos ingresos adicionales de $3$. Hay $3$ unidades de esta verdura, y todas se estropean al final del primer día.
Al vender la verdura de tipo $2$, cada unidad proporciona unos ingresos de $2$ y su primera venta proporciona unos ingresos adicionales de $5$. Hay $8$ unidades de esta verdura: $3$ se estropean al final del primer día, $3$ al final del segundo y $2$ al final del tercero.
Si solo se vende durante $1$ día, se deben vender $2$ unidades del primer tipo y $1$ unidad del segundo.
En este caso, los ingresos del primer tipo son $2\times 3+3$ y los del segundo son $1\times 2+5$. Los ingresos totales son $(2\times 3+3)+(1\times 2+5)=16$.
Si se vende durante $3$ días, el primer día se deben vender $3$ unidades del primer tipo; el segundo día, $3$ unidades del segundo tipo (eligiendo las $3$ unidades que se estropearían al final de ese segundo día); y el tercer día, $2$ unidades del segundo tipo.
En este caso, los ingresos del primer tipo son $3\times 3+3$ y los del segundo son $(3+2)\times 2+5$. Los ingresos totales son $(3\times 3+3)+[(3+2)\times 2+5]=27$.
Subtareas
| Caso de prueba | $n$ | $m$ | $p_j$ | Propiedad 1 | Propiedad 2 |
|---|---|---|---|---|---|
| $1$ | $\leq 2$ | $\leq 10$ | $\leq 10^3$ | No | No |
| $2$ | $\leq 3$ | $\leq 10$ | $\leq 10^3$ | No | No |
| $3$ | $\leq 4$ | $\leq 10$ | $\leq 10^3$ | No | No |
| $4$ | $\leq 10^3$ | $\leq 10$ | $\leq 2$ | No | No |
| $5$ | $\leq 10^3$ | $\leq 10$ | $\leq 3$ | No | No |
| $6$ | $\leq 10^3$ | $\leq 10$ | $\leq 4$ | No | No |
| $7$ | $\leq 4$ | $\leq 1$ | $\leq 4$ | No | No |
| $8$ | $\leq 6$ | $\leq 2$ | $\leq 6$ | No | No |
| $9$ | $\leq 8$ | $\leq 1$ | $\leq 8$ | No | No |
| $10$ | $\leq 10$ | $\leq 2$ | $\leq 10$ | No | No |
| $11$ | $\leq 20$ | $\leq 3$ | $\leq 20$ | No | No |
| $12$ | $\leq 10^2$ | $\leq 10$ | $\leq 10^2$ | Sí | No |
| $13$ | $\leq 10^2$ | $\leq 10$ | $\leq 10^2$ | No | Sí |
| $14$ | $\leq 10^2$ | $\leq 10$ | $\leq 10^2$ | No | No |
| $15$ | $\leq 10^2$ | $\leq 10$ | $\leq 10^2$ | No | No |
| $16$ | $\leq 10^3$ | $\leq 10$ | $\leq 10^3$ | Sí | Sí |
| $17$ | $\leq 10^3$ | $\leq 10$ | $\leq 10^3$ | Sí | No |
| $18$ | $\leq 10^3$ | $\leq 10$ | $\leq 10^3$ | No | Sí |
| $19$ | $\leq 10^3$ | $\leq 10$ | $\leq 10^3$ | No | No |
| $20$ | $\leq 10^3$ | $\leq 10$ | $\leq 10^3$ | No | No |
| $21$ | $\leq 10^5$ | $\leq 10$ | $\leq 10^5$ | Sí | Sí |
| $22$ | $\leq 10^5$ | $\leq 10$ | $\leq 10^5$ | Sí | No |
| $23$ | $\leq 10^5$ | $\leq 10$ | $\leq 10^5$ | No | Sí |
| $24$ | $\leq 10^5$ | $\leq 10$ | $\leq 10^5$ | No | No |
| $25$ | $\leq 10^5$ | $\leq 10$ | $\leq 10^5$ | No | No |
Propiedad 1: todos los $s_i$ son $0$.
Propiedad 2: todos los $x_i$ son $0$.
En todos los datos de prueba se garantiza que los $p_j$ de las $k$ preguntas son distintos entre sí.
En todos los datos de prueba se garantiza que $0<a_i,c_i\leq 10^9$ y $0\leq s_i,x_i\leq 10^9$.