16448번 - Gasolina 다국어

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 D_i (1 ≤ D_i ≤ 10⁴), representando as demandas, em litros de gasolina, dos postos i = 1, 2, . . . , P, nessa ordem. A terceira linha contém R inteiros E_i (1 ≤ E_i ≤ 10⁴), 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 ≤ 10⁶), 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.