Description

After many days' journey through the great Australian outback, you have finally arrived at the great city of Cobar with nothing but a small backpack. Enamoured by the wonder and beauty of its markets, you decide to become a merchant and make Cobar your new home. Cobar has $N$ markets, numbered from $1$ to $N$, connected by $M$ one-way footpaths, each taking a particular number of minutes to walk along.

The markets of Cobar trade in $K$ different items, numbered from $1$ to $K$. Each market has a fixed price for buying or selling each item. Not every market will trade in every item, and it is possible that for any given item, a market may only support buying it, but not selling it, or vice-versa. You may assume that each market that has a given item for sale has an infinite quantity of it available, and similarly, if a market wants to buy a given item, it is willing to buy it repeatedly, forever.

To earn money as quickly as possible, you would like to find the most efficient profit cycle. A profit cycle is a walk through Cobar that starts at some market $v$ with your backpack empty, continues along Cobar's footpaths and through its markets (possibly buying and selling items along the way), and finally returns to $v$, again with an empty backpack. It may visit a market and/or walk along a footpath multiple times. Once an item is bought, it must be placed immediately in your backpack and since your backpack is small, it can only hold up to a single item at any point in time. You may assume that you are always able to buy an item if it is available, regardless of the amount of money you possess so far and that you are prohibited from selling an item that you do not possess.

The profit earned from such a cycle is the total amount of money you earned from selling items, minus the total amount of money you spent buying them. The duration of a cycle is the total number of minutes you spend walking along its constituent footpaths. The efficiency of a profit cycle is the profit earned from it, divided by its duration. Note that a profit cycle that does not involve buying or selling any items has an efficiency of $0$.

Your task is to find the maximum efficiency among all profit cycles with strictly positive duration. You should report this value rounded down, to the nearest integer. If no such profit cycle exists, you should report 0.

Input

Your program should read from standard input.

The first line will contain 3 integers, $N$, $M$ and $K$: the number of markets, footpaths and items respectively.

$N$ lines follow. The ith of these lines contains $2K$ integers $B_{i,1},$ $S_{i,1},$ $B_{i,2},$ $S_{i,2},$ $\ldots,$ $B_{i,K},$ $S_{i,K}$ describing a market. For all $1 ≤ j ≤ K$, the pair of integers $B_{i,j}$ and $S_{i,j}$ describe the price at which you can buy and sell item $j$ at market $i$, respectively. If an item cannot be bought or sold, then -1 will be used as a placeholder.

$M$ lines follow. The pth of these contains 3 integers, $V_p$, $W_p$ and $T_p$, describing a one-way footpath from market $V_p$ to another market $W_p$, taking $T_p$ minutes to traverse.

Output

Your program should write to standard output.

Print a single integer, the maximum efficiency among all profit cycles, rounded down to the nearest integer.

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

Limits And Hints

For all subtasks,

• $1 ≤ N ≤ 100,$ $1 ≤ M ≤ 9,900,$ $1 ≤ K ≤ 1000,$
• and for all items which can be bought/sold, $0 < S_{i,j} ≤ Bi,j ≤ 10^9$ for all $1 ≤ i ≤ N$ and for all $1 ≤ j ≤ K$.
• Additionally, $V_p ≠ W_p$ and $1 ≤ T_p ≤ 10^7$ for all $1 ≤ p ≤ M$,
• and there does not exist any pair of edges $1 ≤ p < q ≤ M$ such that $(Vp, Wp) = (Vq, Wq)$.