떠돌이 상인

시간 제한2초메모리 제한512 MB

요약

가중치가 있는 방향 그래프와 각 시장의 K개 품목 매매 가격이 주어질 때, 한 번에 한 품목만 거래하며 닫힌 보행을 돌 때 이익을 시간으로 나눈 값의 최댓값을 구해 내림한 정수를 출력한다.

난이도: 어려움10점 중 9점
유형: 그래프, 최단 경로, 이분 탐색, 동적 계획법
정답자: 아직 제출이 없습니다

문제

오스트레일리아 내륙을 오래 여행한 끝에 당신은 작은 배낭 하나만 메고 코바라는 도시에 도착했습니다. 시장의 활기에 매료된 당신은 상인이 되어 이곳에 정주하기로 했습니다. 코바에는 $1$ 부터 $N$ 까지 번호가 붙은 $N$ 개의 시장이 있으며, 시장은 이동에 정해진 시간이 걸리는 $M$ 개의 일방통행 오솔길로 연결되어 있습니다.

코바의 시장에서는 $1$ 부터 $K$ 까지 번호가 붙은 $K$ 가지 물품이 거래됩니다. 각 시장은 물품마다 매입가와 매도가를 정해 둡니다. 모든 시장이 모든 물품을 다루는 것은 아니며, 특정 물품은 매입만 가능하거나 매도만 가능할 수도 있습니다. 판매 중인 물품은 재고가 무한하다고 가정하고, 매입 의사가 있는 시장도 횟수 제한 없이 계속 사들인다고 가정합니다.

빨리 돈을 벌기 위해 가장 효율적인 수익 순환을 찾고자 합니다. 수익 순환은 빈 배낭으로 어떤 시장 $v$ 에서 출발해 오솔길을 따라 이동하면서 물품을 사고팔고, 다시 빈 배낭으로 $v$ 로 돌아오는 도보 경로입니다. 같은 시장이나 오솔길을 여러 번 지나도 됩니다. 물품을 사면 즉시 배낭에 넣어야 하며, 배낭은 한 번에 최대 한 개의 물품만 담을 수 있습니다. 판매 중인 물품은 보유 금액과 무관하게 항상 살 수 있다고 가정하고, 들고 있지 않은 물품은 팔 수 없습니다.

수익 순환의 수익은 물품을 팔아 얻은 금액에서 사들이는 데 쓴 금액을 뺀 값입니다. 소요 시간은 경로에 포함된 오솔길 이동 시간의 합입니다. 효율은 수익을 소요 시간으로 나눈 값입니다. 물품을 전혀 거래하지 않은 순환의 효율은 $0$ 입니다.

이동 시간이 양수인 모든 수익 순환 중에서 효율의 최댓값을 구하고, 소수점 이하는 버린 정수를 보고해야 합니다. 그런 순환이 존재하지 않으면 $0$ 을 보고합니다.

입력

프로그램은 표준 입력에서 읽어야 합니다.

첫째 줄에는 시장의 수와 오솔길의 수와 물품의 수를 나타내는 세 정수 $N$ , $M$ , $K$ 가 주어집니다.

이어서 $N$ 개의 줄이 주어집니다. 이 중 $i$ 번째 줄에는 시장을 설명하는 $2K$ 개의 정수 $B_{i,1}, S_{i,1}, B_{i,2}, S_{i,2}, \dots, B_{i,K}, S_{i,K}$ 가 주어집니다. 모든 $1 \le j \le K$ 에 대해 정수 쌍 $B_{i,j}$ 와 $S_{i,j}$ 는 시장 $i$ 에서 물품 $j$ 를 사거나 파는 가격을 각각 나타냅니다. 살 수 없거나 팔 수 없는 물품은 자리 표시자로 $-1$ 이 사용됩니다.

이어서 $M$ 개의 줄이 주어집니다. 이 중 $p$ 번째 줄에는 시장 $V_p$ 에서 다른 시장 $W_p$ 로 이동하며 $T_p$ 분이 걸리는 일방통행 오솔길을 설명하는 세 정수 $V_p$ , $W_p$ , $T_p$ 가 주어집니다.

출력

프로그램은 표준 출력에 써야 합니다.

모든 수익 순환 중 최대 효율을 소수점 이하는 버려서 하나의 정수로 출력합니다.

제한

모든 하위 과제에서 $1 \le N \le 100$ , $1 \le M \le 9900$ , $1 \le K \le 1000$ 이며, 사고팔 수 있는 모든 물품에 대해 모든 $1 \le i \le N$ 과 모든 $1 \le j \le K$ 에서 $0 < S_{i,j} \le B_{i,j} \le 1000000000$ 입니다. 또한 모든 $1 \le p \le M$ 에 대해 $V_p \ne W_p$ 이고 $1 \le T_p \le 10000000$ 이며, 서로 다른 두 오솔길 $1 \le p < q \le M$ 에 대해 순서쌍 $(V_p, W_p)$ 와 $(V_q, W_q)$ 가 같은 경우는 존재하지 않습니다.

힌트

표본 사례에는 $1$ 에서 $2$ 를 거쳐 $3$ 을 지나 $1$ 로 돌아오는 순환과 $1$ 에서 $4$ 를 거쳐 $3$ 을 지나 $1$ 로 돌아오는 순환, 두 가지 순환을 고려합니다.

첫 번째 순환은 이동에 $3 + 3 + 1 = 7$ 분이 걸립니다. 이 순환에서 가장 수익이 큰 거래는 시장 $1$ 에서 물품 $2$ 를 매입하고 시장 $2$ 에서 매도한 뒤, 시장 $2$ 에서 물품 $1$ 을 매입해 시장 $3$ 을 거쳐 운반하고 마지막으로 시장 $1$ 에서 매도하는 것입니다. 이에 따라 수익은 $-5 + 15 - 6 + 9 = 13$ 이며, $13/7$ 을 내림하면 효율은 $1$ 입니다.

두 번째 순환은 이동에 $1 + 1 + 1 = 3$ 분이 걸립니다. 가장 수익이 큰 거래는 시장 $1$ 에서 물품 $2$ 를 매입해 시장 $4$ 에서 매도한 뒤 시장 $3$ 을 거쳐 시장 $1$ 로 돌아오는 것으로, 수익은 $-5 + 11 = 6$ 이며 $6/3 = 2$ 이므로 효율은 $2$ 입니다.

따라서 코바에서 가능한 모든 수익 순환 중 가장 좋은 효율은 $2$ 입니다.

예제1

예제 1

입력

4 5 2
10 9 5 2
6 4 20 15
9 7 10 9
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1

예상 출력