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.|

VIGILANC - Vigilância

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

Adicionado por:Ricardo Oliveira [UFPR]
Data:2014-08-11
Tempo limite:0.5s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Seletiva UFPR 2014

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.