Sau nhiều ngày băng qua vùng hoang dã rộng lớn của nước Úc, cuối cùng bạn đã đến thành phố Cobar tráng lệ với hành trang chỉ là một chiếc ba lô nhỏ. Say mê trước vẻ đẹp và sự kỳ diệu của các khu chợ nơi đây, bạn quyết định trở thành một thương gia và chọn Cobar làm quê hương mới. Cobar có \(N\) khu chợ, được đánh số từ \(1\) đến \(N\), nối với nhau bởi \(M\) đường đi bộ một chiều, mỗi đường cần một số phút nhất định để đi qua.

Các khu chợ ở Cobar giao dịch \(K\) mặt hàng khác nhau, được đánh số từ \(1\) đến \(K\). Mỗi khu chợ có một mức giá cố định để mua hoặc bán từng mặt hàng. Không phải khu chợ nào cũng giao dịch mọi mặt hàng; với một mặt hàng nhất định, một khu chợ có thể chỉ cho phép mua mà không cho phép bán, hoặc ngược lại. Có thể giả sử mỗi khu chợ bán một mặt hàng nào đó luôn có số lượng vô hạn, và tương tự, nếu một khu chợ muốn mua một mặt hàng thì khu chợ đó sẵn sàng mua đi mua lại mãi mãi.

Để kiếm tiền nhanh nhất có thể, bạn muốn tìm một chu trình sinh lời hiệu quả nhất. Một chu trình sinh lời là một hành trình trong Cobar, bắt đầu tại một khu chợ \(v\) với ba lô rỗng, tiếp tục dọc theo các đường đi bộ và qua các khu chợ của Cobar (có thể mua và bán các mặt hàng trên đường đi), rồi cuối cùng quay lại \(v\) với ba lô lại rỗng. Hành trình có thể ghé một khu chợ và/hoặc đi qua một đường đi bộ nhiều lần. Khi mua một mặt hàng, bạn phải lập tức đặt nó vào ba lô; vì ba lô nhỏ nên tại mọi thời điểm nó chỉ có thể chứa tối đa một mặt hàng. Có thể giả sử rằng bạn luôn mua được một mặt hàng nếu mặt hàng đó có bán, bất kể số tiền hiện có của bạn, và bạn không được phép bán một mặt hàng mà mình không sở hữu.

Lợi nhuận của một chu trình như vậy bằng tổng số tiền thu được từ việc bán hàng trừ đi tổng số tiền đã chi để mua hàng. Thời lượng của chu trình là tổng số phút đi bộ trên các đường đi tạo nên chu trình. Hiệu suất của một chu trình sinh lời bằng lợi nhuận của nó chia cho thời lượng. Lưu ý rằng một chu trình sinh lời không mua hoặc bán bất kỳ mặt hàng nào có hiệu suất bằng \(0\).

Nhiệm vụ của bạn là tìm hiệu suất lớn nhất trong tất cả các chu trình sinh lời có thời lượng dương. Hãy ghi giá trị này sau khi làm tròn xuống số nguyên gần nhất. Nếu không tồn tại chu trình sinh lời như vậy, hãy ghi \(0\).

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(N\), \(M\) và \(K\): lần lượt là số khu chợ, số đường đi bộ và số mặt hàng.

\(N\) dòng tiếp theo mô tả các khu chợ. Dòng thứ \(i\) chứa \(2K\) số nguyên \(B_{i,1}, S_{i,1}, B_{i,2}, S_{i,2}, \ldots, B_{i,K}, S_{i,K}\). Với mọi \(1 \le j \le K\), cặp số nguyên \(B_{i,j}\) và \(S_{i,j}\) lần lượt mô tả mức giá mà bạn có thể mua và bán mặt hàng \(j\) tại khu chợ \(i\). Nếu không thể mua hoặc bán một mặt hàng, giá trị tương ứng được thay bằng \(-1\).

\(M\) dòng tiếp theo mô tả các đường đi bộ. Dòng thứ \(p\) chứa ba số nguyên \(V_p\), \(W_p\) và \(T_p\), mô tả một đường đi bộ một chiều từ khu chợ \(V_p\) đến khu chợ \(W_p\), cần \(T_p\) phút để đi qua.

Dữ liệu ra

In ra một số nguyên duy nhất là hiệu suất lớn nhất trong tất cả các chu trình sinh lời, được làm tròn xuống số nguyên gần nhất.

Phân nhóm

Trong tất cả các subtasks:

• \(1 \le N \le 100\);
• \(1 \le M \le 9900\);
• \(1 \le K \le 1000\);
• với mọi mặt hàng có thể được mua/bán, \(0 \le S_{i,j} \le B_{i,j} \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\) và \(1 \le j \le K\);
• \(V_p \ne W_p\) và \(1 \le T_p \le 10\,000\,000\) với mọi \(1 \le p \le M\);
• không tồn tại hai cạnh \(1 \le p < q \le M\) sao cho \((V_p, W_p) = (V_q, W_q)\).

Ví dụ

Phản hồi cho ví dụ sau sẽ được cung cấp dưới dạng "Sample Data" khi nộp bài.

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

2

Giải thích

Trong ví dụ, xét hai chu trình "1 đến 2 đến 3 đến 1" và "1 đến 4 đến 3 đến 1".

Với chu trình "1 đến 2 đến 3 đến 1", thời gian đi hết chu trình là \(7\) phút, bằng \(3 + 3 + 1\). Cách giao dịch có lợi nhất trên chu trình này là mua mặt hàng \(2\) tại khu chợ \(1\) (tốn \(5\)), bán nó tại khu chợ \(2\) (thu \(15\)), ngay lập tức mua mặt hàng \(1\) tại khu chợ \(2\) (tốn \(6\)), mang mặt hàng \(1\) qua khu chợ \(3\), rồi bán nó tại khu chợ \(1\) (thu \(9\)). Vì vậy lợi nhuận trên chu trình này là \(-5 + 15 - 6 + 9 = 13\). Giá trị \(13/7\) làm tròn xuống cho hiệu suất bằng \(1\).

Với chu trình "1 đến 4 đến 3 đến 1", thời gian đi hết chu trình là \(3\) phút, bằng \(1 + 1 + 1\). Cách giao dịch có lợi nhất trên chu trình này là mua mặt hàng \(2\) tại khu chợ \(1\) (tốn \(5\)), bán nó tại khu chợ \(4\) (thu \(11\)), rồi đi qua khu chợ \(3\) và trở lại khu chợ \(1\). Vì vậy lợi nhuận trên chu trình này là \(-5 + 11 = 6\). Giá trị \(6/3\) làm tròn xuống cho hiệu suất bằng \(2\).

Do đó, hiệu suất tốt nhất của một chu trình sinh lời tại Cobar là \(2\).

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2017: Travelling Merchant.