Maximum Cycle Profit Efficiency

You are a merchant planning your business in the city of Koba. There are N markets numbered from 1 to N connected by M one‐way roads. Each road from market u to market v takes a certain amount of time to traverse.

The city trades K different products (numbered from 1 to K). In every market, each product may be available for purchase or sale – sometimes both. When a market sells a product, you can buy it (with no limit on quantity) at the given price; when a market buys a product, you can sell any amount of that product at its buying price. Note that a market might offer only one side of the transaction for a given product.

You start with an empty bag (which can hold at most one product at a time) and plan to follow a cycle (a route starting and ending at the same market) in which you may perform several transactions. At any market you may choose to buy an available product (if you are empty) or sell the product you are carrying (if the market buys it). Once you buy an item, you must carry it until you sell it. The profit of a cycle is the total money gained by selling minus the money spent buying, and the total time is the sum of the travel times along the roads used. (Transactions do not consume time.)

The profit efficiency of a cycle is defined as \[ \text{efficiency} = \frac{\text{total profit}}{\text{total time}}, \] with the understanding that any cycle that does not involve any transaction (hence, profit = 0) has an efficiency of 0. Note that only cycles whose total time is positive are considered. Your task is to find, among all cycles with strictly positive total time, the maximum profit efficiency. Output the answer as an integer by rounding down (taking the floor) the maximum efficiency. If no cycle can produce positive profit, output 0.

Note: The cycle may traverse the same market or road multiple times. However, your bag can carry at most one product at any time and you must sell the current product before buying another.

inputFormat

The first line contains three integers N, M and K --- the number of markets, the number of roads, and the number of products, respectively.

The next M lines each contain three integers u, v, and t, representing a one‐way road from market u to market v that takes t time to traverse.

This is followed by N blocks describing each market in order from market 1 to market N. For each market, the first line of the block contains a single integer P indicating the number of trade records for that market. Each of the next P lines contains three integers: p, a and b.

• p is the product number (1 ≤ p ≤ K).
• If a is not -1, it means the market sells product p at price a (i.e. you can buy product p for a money). If a is -1, then product p is not available for purchase here.
• If b is not -1, it means the market buys product p at price b (i.e. you can sell product p here for b money). If b is -1, then the market does not buy product p.

It is guaranteed that 1 ≤ N, M, K ≤ (small limits) so that a solution using state expansion is feasible.

outputFormat

Output a single integer --- the floor of the maximum profit efficiency achievable by any cycle with positive total time. If no cycle can produce positive profit, output 0.

sample

3 3 2
1 2 3
2 3 4
3 1 5
2
1 5 -1
2 -1 10
1
1 -1 7
2
1 6 9
2 8 -1

0