Xiao N é o administrador de um armazém de legumes e é responsável por planejar as vendas dos legumes.
O armazém contém $n$ tipos de legumes. Xiao N precisa considerar as características dos diferentes legumes e os diversos fatores envolvidos para elaborar um plano de vendas adequado que obtenha a maior receita possível.
Ao calcular a receita das vendas, cada unidade vendida do tipo $i$ gera uma receita de $a_i$.
Além disso, como a política incentiva os comerciantes a diversificar as vendas, a primeira venda do tipo $i$ gera uma receita adicional de $s_i$.
No início das atividades, o estoque do tipo $i$ é de $c_i$ unidades.
No entanto, os legumes conservam-se por um período muito limitado e não podem ser vendidos depois de estragarem. O inteligente Xiao N já calculou quando cada unidade estraga: para o tipo $i$, há um parâmetro de conservação $x_i$, e $x_i$ unidades estragam ao final de cada dia, até que todos os legumes tenham estragado. (Atenção: o momento em que cada unidade estraga é fixo e não muda em função das vendas.)
Formalmente, para todo inteiro positivo $d$ que satisfaça $d\times x_i\leq c_i$, há $x_i$ unidades que estragam ao final do dia $d$.
Em particular, se $(d-1)\times x_i\leq c_i<d\times x_i$, então $c_i-(d-1)\times x_i$ unidades estragam ao final do dia $d$.
Observe que $x_i=0$ significa que esse tipo de legume não estraga.
Além disso, a quantidade total de legumes vendidos em cada dia também é limitada: não pode ultrapassar $m$ unidades.
Agora, Xiao N tem $k$ perguntas e gostaria da sua ajuda para fazer os cálculos. Cada pergunta tem a seguinte forma: dado $p_j$, se as vendas durarem $p_j$ dias, qual é a maior receita possível?
Entrada
Leia os dados do arquivo vegetables.in.
A primeira linha contém três inteiros positivos $n,m,k$, que representam, respectivamente, o número de tipos de legumes, o limite da quantidade total de legumes que podem ser vendidos por dia e o número de perguntas de Xiao N.
Cada uma das próximas $n$ linhas contém quatro inteiros não negativos que descrevem as características de um tipo de legume: $a_i,s_i,c_i,x_i$, nessa ordem, com os significados definidos acima.
Cada uma das próximas $k$ linhas contém um inteiro não negativo $p_j$, com o significado definido acima.
Saída
Escreva no arquivo vegetables.out.
Imprima $k$ linhas, cada uma contendo um inteiro. O número na linha $i$ representa a resposta à pergunta $i$.
Exemplos
Entrada 1
2 3 2 3 3 3 3 2 5 8 3 1 3
Saída 1
16 27
Exemplo 2
Consulte vegetables/vegetables2.in e vegetables/vegetables2.ans no diretório do participante.
Exemplo 3
Consulte vegetables/vegetables3.in e vegetables/vegetables3.ans no diretório do participante.
Explicação do exemplo 1
Há dois tipos de legumes:
Cada unidade vendida do primeiro tipo gera uma receita de $3$, e a primeira venda desse tipo gera uma receita adicional de $3$. Há $3$ unidades desse tipo, e todas estragam ao final do primeiro dia.
Cada unidade vendida do segundo tipo gera uma receita de $2$, e a primeira venda desse tipo gera uma receita adicional de $5$. Há $8$ unidades desse tipo: $3$ estragam ao final do primeiro dia, $3$ ao final do segundo dia e $2$ ao final do terceiro dia.
Se as vendas durarem apenas 1 dia, devem ser vendidas $2$ unidades do primeiro tipo e $1$ unidade do segundo tipo.
Nesse caso, a receita do primeiro tipo é $2\times 3+3$, e a do segundo tipo é $1\times 2+5$. A receita total é $(2\times 3+3)+(1\times 2+5)=16$.
Se as vendas durarem apenas 3 dias, devem ser vendidas $3$ unidades do primeiro tipo no primeiro dia, $3$ unidades do segundo tipo no segundo dia (escolhendo as $3$ unidades que estragam ao final do segundo dia) e $2$ unidades do segundo tipo no terceiro dia.
Nesse caso, a receita do primeiro tipo é $3\times 3+3$, e a do segundo tipo é $(3+2)\times 2+5$. A receita total é $(3\times 3+3)+[(3+2)\times 2+5]=27$.
Subtarefas
| Caso de teste | $n$ | $m$ | $p_j$ | Propriedade 1 | Propriedade 2 |
|---|---|---|---|---|---|
| $1$ | $\leq 2$ | $\leq 10$ | $\leq 10^3$ | Não | Não |
| $2$ | $\leq 3$ | ||||
| $3$ | $\leq 4$ | ||||
| $4$ | $\leq 10^3$ | $\leq 2$ | |||
| $5$ | $\leq 3$ | ||||
| $6$ | $\leq 4$ | ||||
| $7$ | $\leq 4$ | $\leq 1$ | |||
| $8$ | $\leq 6$ | $\leq 2$ | $\leq 6$ | ||
| $9$ | $\leq 8$ | $\leq 1$ | $\leq 8$ | ||
| $10$ | $\leq 10$ | $\leq 2$ | $\leq 10$ | ||
| $11$ | $\leq 20$ | $\leq 3$ | $\leq 20$ | ||
| $12$ | $\leq 10^2$ | $\leq 10$ | $\leq 10^2$ | Sim | Não |
| $13$ | Não | Sim | |||
| $14$ | Não | ||||
| $15$ | |||||
| $16$ | $\leq 10^3$ | $\leq 10^3$ | Sim | Sim | |
| $17$ | Não | ||||
| $18$ | Não | Sim | |||
| $19$ | Não | ||||
| $20$ | |||||
| $21$ | $\leq 10^5$ | $\leq 10^5$ | Sim | Sim | |
| $22$ | Não | ||||
| $23$ | Não | Sim | |||
| $24$ | Não | ||||
| $25$ |
Propriedade 1: todos os $s_i$ são iguais a $0$.
Propriedade 2: todos os $x_i$ são iguais a $0$.
Em todos os dados de teste, é garantido que os valores de $p_j$ nas $k$ perguntas são distintos entre si.
Em todos os dados de teste, é garantido que $0<a_i,c_i\leq 10^9$ e $0\leq s_i,x_i\leq 10^9$.