SPOJ Brasil

A rua que liga a entrada do campus ao prédio do Departamento de Informática (DINF) é uma das mais utilizadas no centro politécnico. Por isso, a Prefeitura da Cidade Universitária (PCU) investiu em um esquema de vigilância para garantir a segurança na rua.

A rua é composta por N segmentos contínuos numerados sequencialmente de 1 a N (o segmento 1 é o mais próximo à entrada, e o segmento N é o mais próximo ao DINF).

A prefeitura comprou C câmeras, numeradas de 1 a C. A câmera i (1 ≤ i ≤ C), quando ligada, filma todos os segmentos da rua entre a_i e b_i, inclusive (1 ≤ a_i ≤ b_i ≤ N).

O consumo de energia de cada câmera é dado de maneira peculiar. Um vetor (w₁, w₂, ..., w_M) é fornecido pelo fabricante das câmeras. A câmera i, quando ligada, consome  unidades de energia, onde c_i e d_i (1 ≤ c_i ≤ d_i ≤ M) são inteiros associados a cada câmera.

Sua tarefa é determinar quais câmeras devem estar simultaneamente ligadas para que todos os segmentos da rua sejam filmados, e para que o total de energia gasta pelas câmeras seja mínima.

Entrada

A entrada inicia com uma linha contendo três inteiros, N, M e C (1 ≤ N ≤ 10³, 1 ≤ C ≤ 5×10³, 1 ≤ M ≤ 10⁶). A segunda linha contém M inteiros w₁, w₂, ..., w_M (1 ≤ w_i ≤ 10³ para 1 ≤ i ≤ M). As próximas C linhas contém a descrição das câmeras. Cada linha contém quatro inteiros a_i, b_i, c_i e d_i (1 ≤ a_i ≤ b_i ≤ N, 1 ≤ ci ≤ d_i ≤ M).

Saída

Se não é possível filmar toda a rua simultaneamente, imprima impossivel. Caso contrário, imprima a menor quantidade de energia necessária para filmá-la.

Examplos

Entrada:
5 5 4
1 3 5 7 9
1 3 1 5
2 4 2 4
3 5 1 3
2 5 2 5

Saída:
34

Entrada:
5 4 2
8 3 1 5
1 3 4 4
5 5 2 3

Saída:
impossivel