Gasolina
Por Maratona de Programação SBC 2018 
Brazil
Por Maratona de Programação SBC 2018 Brazil
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.
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 ≤ I ≤ P e 1 ≤ J ≤ R 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.
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 |