#include "bits/stdc++.h"
using namespace std;
#define ll long long
const int N = 1e2 + 5;
vector <pair <int, int>> v[N];
ll n, m, k, ans = 1e9;
vector <vector <ll>> dis, e, b, s;
bool check(ll x) {
e.assign(n+1, vector <ll> (n+1, 0));
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
for(int x = 1; x <= k; x++) {
if(b[i][x] == -1 or s[j][x] == -1) continue;
e[i][j] = max(e[i][j], (s[j][x] - b[i][x]));
}
e[i][j] -= (x * dis[i][j]);
e[i][j] *= (-1);
}
}
for(int x = 1; x <= n; x++) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
e[i][j] = min(e[i][j], e[i][x] + e[x][j]);
}
}
}
for(int i = 1; i <= n; i++) {
if(e[i][i] <= 0) return true;
}
return false;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m >> k;
b.assign(n+1, vector <ll> (k+1, 0)), s.assign(n+1, vector <ll> (k+1, 0));
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= k; j++) {
cin >> b[i][j] >> s[i][j];
}
}
dis.assign(n+1, vector <ll> (n+1, 1e15));
for(int i = 1; i <= m; i++) {
int u1, u2, w;
cin >> u1 >> u2 >> w;
v[u1].push_back({u2, w});
dis[u1][u2] = 2;
}
for(int x = 1; x <= n; x++) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
dis[i][j] = min(dis[i][j], dis[i][x] + dis[x][j]);
}
}
}
int l = 0, r = 1e9;
while(l <= r) {
int md = (l + r) / 2;
if(check(md)) {
l = md+1;
ans = md;
}
else {
r = md-1;
}
}
cout << ans;
return 0;
}
