#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 1, MOD = 1e9 + 7;
typedef long long ll;
#define int long long
int n,m,k,b[N][1001],s[N][1001];
vector<pair<int,int>> g[N],gt[N][N];
vector<int> ord;
ll dp[N],val[N][N];
int ok[N][N],timer = 0,used[N],curv = 1,cost[101][101];
void dfs(int v){
used[v] = timer;
for(auto [to,w]:g[v]){
if(used[to] != timer){
gt[curv][v].push_back({to,w});
dfs(to);
}else{
if(to == curv){
// cout << curv << ' ' << v << '\n';
ok[curv][v] = 1;
val[curv][v] = w;
}
}
}
}
int mid;
ll res = -1e18;
void dfs1(int v,ll cur,vector<int> &prs){
for(int j:prs){
dp[v] = max(dp[v],dp[j] + cost[j][v]);
}
if(ok[curv][v]){
for(int j:prs){
dp[v] = max(dp[v],dp[j] + cost[j][1]);
}
dp[v] = max(0ll,cost[v][1]) + dp[v];
res = max(res,dp[v] - (cur + val[curv][v]) * mid);
// cout << curv << ' ' << v << ' ' << dp[v] << ' ' << (cur + val[curv][v]) * mid << '\n';
}
for(auto [to,w]:gt[curv][v]){
prs.push_back(v);
dfs1(to,cur + w,prs);
prs.pop_back();
}
}
bool check(){
res = -1e18;
for(curv = 1;curv <= n;curv++){
for(int i = 1;i <=n;i++){
dp[i] = 0;
}
vector<int> em;
dfs1(curv,0,em);
}
return (res >= 0);
}
void test(){
cin >> n >> m >> k;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= k;j++){
cin >> b[i][j] >> s[i][j];
}
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
if(i == j) continue;
cost[i][j] = -1e18;
for(int f = 1;f <= k;f++){
if(b[i][f] != -1 && s[j][f] != -1){
cost[i][j] = max(cost[i][j],s[j][f]-b[i][f]);
}
}
}
}
for(int i = 1;i <= m;i++){
int x,y,w;
cin >> x >> y >> w;
g[x].push_back({y,w});
}
for(;curv <= n;curv++){
++timer;
dfs(curv);
}
ll l = 0,r = 1e9;
while(r - l > 1){
mid = (l + r) >> 1;
if(check()){
l = mid;
}else{
r = mid;
}
}
cout << l;
}
main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int T = 1;
// cin >> T;
while (T--)
test();
}
