시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 1 1 100.000%

문제

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.

예제 입력 1

3 2 5
20 10 10
30 20
1 1 2
2 1 1
2 2 3
3 1 4
3 2 5

예제 출력 1

4

예제 입력 2

3 2 5
20 10 10
25 30
1 1 3
2 1 1
2 2 4
3 1 2
3 2 5

예제 출력 2

5

예제 입력 3

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

예제 출력 3

-1

예제 입력 4

1 2 2
40
30 10
1 1 100
1 2 200

예제 출력 4

200