#include <bits/stdc++.h> using namespace std; #define int long long signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, m, k; cin >> n >> m >> k; vector<vector<pair<int, int>>> trade(n+1, vector<pair<int, int>>(k)); for(int i = 1; i <= n; i++){ for(int y = 0; y < k; y++){ cin >> trade[i][y].first >> trade[i][y].second; } } //f = buy, s = sell vector<vector<int>> g(n+1, vector<int>(n+1, 1e18)); for(int y = 0; y < m; y++){ int u, v, p; cin >> u >> v >> p; g[u][v] = p; } for(int i = 1; i <= n; i++){ g[i][i] = 0; } for(int y = 1; y <= n; y++){ for(int i = 1; i <= n; i++){ for(int z = 1; z <= n; z++){ g[i][z] = min(g[i][z], g[i][y] + g[y][z]); } } } vector<vector<int>> mx(n+1, vector<int>(n+1, 0LL)); for(int i = 1; i <= n; i++){ for(int y = 1; y <= n; y++){ for(int z = 0; z < k; z++){ if(trade[y][z].second == -1 || trade[i][z].first == -1) continue; mx[i][y] = max(mx[i][y], trade[y][z].second - trade[i][z].first); } } } int ns = 0; for(int i = 1; i <= n; i++){ vector<pair<int, int>> dp(n+1, {-1e18, 1}); dp[i] = {0, 0}; for(int aw = 0; aw < n; aw++){ for(int y = 1; y <= n; y++){ for(int z = 1; z <= n; z++){ if(y == z || dp[y].first == -1e18) continue; auto [c, v] = dp[y]; c += mx[y][z]; v += g[y][z]; //c/v > dp[z].first/dp[z].second long double per = c * dp[z].second; long double per2 = dp[z].first*v; if(per >= per2 && c/v >= 0){ dp[z] = {c, v}; } } } } // cout << i << " " << dp[i].first << " " << dp[i].second << "\n";; if(dp[i] == make_pair(0LL, 0LL)) continue; int j = (dp[i].first/dp[i].second); ns = max(ns, j); } cout << ns << "\n"; return 0; }