가솔린

화물차 기사들의 파업이 끝난 뒤, Nlogônia의 물류 전문가들은 도시 주유소들의 재고를 채울 계획을 세워야 합니다. 이를 위해 R개의 정유소 재고와 P개의 주유소 수요에 대한 정보를 모았습니다. 또한 계약상의 제약으로 인해 일부 정유소가 특정 주유소에 공급할 수 없습니다. 한 정유소가 어떤 주유소에 공급할 수 있을 때, 연료를 한쪽에서 다른 쪽으로 운반하는 최소 소요 시간을 알고 있습니다.

전문가들의 임무는 모든 주유소의 수요를 완전히 충족시키면서 공급 시간을 최소화하는 것입니다. 정유소에는 충분히 많은 트럭이 있어, 각 트럭이 정유소에서 주유소로 최대 한 번만 운행한다고 가정할 수 있습니다. 각 트럭의 용량은 어떤 주유소의 수요보다 크지만, 한 주유소의 수요를 채우기 위해 여러 정유소를 사용해야 할 수도 있습니다.

여러분의 프로그램은 정유소의 재고를 지키면서 모든 주유소에 연료를 완전히 공급할 수 있는 최소 시간을 구해야 합니다.

입력의 첫 번째 줄에는 세 정수 P, R, C가 주어집니다. 각각 주유소의 수, 정유소의 수, 소요 시간이 주어지는 정유소와 주유소 쌍의 수입니다 (1 ≤ P, R ≤ 1000, 1 ≤ C ≤ 20000). 두 번째 줄에는 P개의 정수 Di (1 ≤ Di ≤ 10⁴)가 주어지며, 이는 i = 1, 2, ..., P 순서대로 주유소의 수요(리터)입니다. 세 번째 줄에는 R개의 정수 Ei (1 ≤ Ei ≤ 10⁴)가 주어지며, 이는 i = 1, 2, ..., R 순서대로 정유소의 재고(리터)입니다. 마지막으로 C개의 줄에는 주유소와 정유소 사이의 소요 시간(분)이 주어집니다. 각 줄에는 세 정수 I, J, T가 주어집니다 (1 ≤ I ≤ P, 1 ≤ J ≤ R, 1 ≤ T ≤ 10⁶). I는 주유소의 번호, J는 정유소의 번호, T는 정유소 J에서 주유소 I로 가는 트럭의 소요 시간입니다. 같은 쌍 (J, I)는 두 번 나오지 않습니다. 모든 쌍이 주어지지는 않으며, 주어지지 않은 쌍에 대해서는 계약상의 제약으로 인해 해당 정유소가 해당 주유소에 공급할 수 없습니다.

모든 주유소에 연료를 완전히 공급할 수 있는 최소 시간(분)을 정수 T로 출력합니다. 불가능한 경우에는 -1을 출력합니다.