Plano de transporte

Time limit: 4000 msMemory limit: 256 MB

Há $N$ depósitos e $K$ lojas. O depósito $i$ dispõe de $s_i$ unidades de um produto, e a loja $j$ pode receber no máximo $d_j$ unidades.

Existem $M$ contratos. O contrato $e$ permite enviar no máximo $c_e$ unidades de seu depósito $u_e$ para sua loja . Contratos distintos podem ligar o mesmo par. Todas as quantidades enviadas devem ser inteiras e não negativas.

Escolha quanto enviar por cada contrato para maximizar a quantidade total enviada, sem ultrapassar o estoque de nenhum depósito, a capacidade de nenhuma loja ou o limite de nenhum contrato. Imprima um plano ótimo; qualquer plano ótimo será aceito.

Input

A primeira linha contém $N$ , $K$ e $M$ . A segunda contém $s_1,\ldots,s_N$ ; a terceira contém . Cada uma das próximas linhas contém , e .

Output

Imprima a quantidade total enviada na primeira linha. Depois, imprima $M$ inteiros, um por linha: a quantidade enviada pelo contrato correspondente, na ordem da entrada. Se $M=0$ , imprima apenas a primeira linha.

Samples

Sample 1

Input

Output

O depósito 1 envia duas unidades para a loja 1 e uma para a loja 2. O depósito 2 envia duas para a loja 2. Os estoques e as capacidades das lojas são totalmente utilizados.

Sample 2

Input

Output

5
4
1

Os dois contratos ligam o mesmo par. Enviar 1 pelo primeiro e 4 pelo segundo é ótimo; enviar 4 pelo primeiro e 1 pelo segundo também seria aceito.