Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

Problem hidden

VIGILANC - Vigilância

no tags 

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 ≤ iC), quando ligada, filma todos os segmentos da rua entre ai e bi, inclusive (1 ≤ ai ≤ biN).

O consumo de energia de cada câmera é dado de maneira peculiar. Um vetor (w1, w2, ..., wM) é fornecido pelo fabricante das câmeras. A câmera i, quando ligada, consome "somatorio de w_j, para c_i <= j <= d_i" unidades de energia, onde ci e di (1 ≤ ci ≤ diM) 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 ≤ 103, 1 ≤ C ≤ 5×103, 1 ≤ M ≤ 106). A segunda linha contém M inteiros w1, w2, ..., wM (1 ≤ wi ≤ 103 para 1 ≤ iM). As próximas C linhas contém a descrição das câmeras. Cada linha contém quatro inteiros ai, bi, ci e di (1 ≤ ai ≤ biN, 1 ≤ ci ≤ diM).

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

Added by:Ricardo Oliveira [UFPR]
Date:2014-08-11
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Seletiva UFPR 2014