URI Online Judge | 2882

Gasolina

Por Maratona de Programação SBC 2018 BR Brazil

Timelimit: 1

Terminada a greve dos caminhoneiros, você e os demais especialistas em logística da Nlogônia agora têm a tarefa de planejar o reabastecimento dos postos da cidade. Para isso, foram coletadas informações sobre os estoques das R refinarias e sobre as demandas dos P postos de gasolina. Além disso, há restrições contratuais que fazem com que algumas refinarias não possam atender alguns postos; quando uma refinaria pode fornecer a um posto, sabe-se o menor tempo de percurso para transportar o combustível de um lugar ao outro.

A tarefa dos especialistas é minimizar o tempo de abastecimento de todos os postos, satisfazendo completamente suas demandas. As refinarias têm uma quantidade suficientemente grande de caminhões, de modo que é possível supor que cada caminhão precisará fazer no máximo uma viagem, de uma refinaria para um posto de gasolina. A capacidade de cada caminhão é maior do que a demanda de qualquer posto, mas pode ser necessário usar mais de uma refinaria para atender a demanda de um posto. Seu programa deve encontrar o tempo mínimo no qual  é possível abastecer totalmente todos os postos, respeitando os estoques das refinarias.

Entrada

A primeira linha da entrada contém três inteiros, P, R e C, respectivamente o número de postos, o número de refinarias e o número de pares de refinaria e posto cujo tempo de percurso será dado (1 ≤ P, R ≤ 1000 e 1 ≤ C ≤ 20000). A segunda linha contém P inteiros Di (1 ≤ Di ≤ 104 ), representando as demandas, em litros de gasolina, dos postos i = 1, 2, . . . , P, nessa ordem. A terceira linha contém R inteiros Ei (1 ≤ Ei ≤ 104 ), representando os estoques, em litros de gasolina, das refinarias i = 1, 2, . . . , R, nessa ordem. Finalmente, as últimas C linhas descrevem tempos de percurso, em minutos, entre postos e refinarias. Cada uma dessas linhas contém três inteiros, I, J e T (1 ≤ IP e 1 ≤ JR e 1 ≤ T ≤ 106 ), onde I é a identificação de um posto, J é a identificação de uma refinaria e T é o tempo do percurso de um caminhão da refinaria J ao posto I. Não haverá pares (J, I) repetidos. Nem todos os pares são informados; caso um par não seja informado, há restrições contratuais que impedem a refinaria de atender o posto.

Saída

Imprima um inteiro T que indica o tempo mínimo em minutos para que todas os postos sejam completamente abastecidos. Caso isso não seja possível, imprima −1.

Exemplos de Entrada Exemplos de Saída

3 2 5

20 10 10

30 20

1 1 2

2 1 1

2 2 3

3 1 4

3 2 5

4

3 2 5

20 10 10

25 30

1 1 3

2 1 1

2 2 4

3 1 2

3 2 5

5

4 3 9

10 10 10 20

10 15 30

1 1 1

1 2 1

2 1 3

2 2 2

3 1 10

3 2 10

4 1 1

4 2 2

4 3 30

-1