实际上是求最短的避雨时间。
首先将每个点拆成两个，一个连接源点，一个连接汇点，连接源点的点的容量为当前单的奶牛数，连接汇点的点为能容纳的奶牛数。
floyd求任意两点互相到达的最短时间，二分最长时间，最大流判断是否可行。
注意路径时间会超过int
/*
最大流SAP
邻接表
思路：基本源于FF方法，给每个顶点设定层次标号，和允许弧。
优化:
1、当前弧优化（重要）。
1、每找到以条增广路回退到断点（常数优化）。
2、层次出现断层，无法得到新流（重要）。
时间复杂度（m*n^2）
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#define ms(a,b) memset(a,b,sizeof a)
using namespace std;
const int INF = ;
long long G[INF][INF];
struct node {
int v, c, next;
} edge[INF*INF * ];
long long pHead[INF*INF], SS, ST, nCnt;
void addEdge (int u, int v, int c) {
edge[++nCnt].v = v; edge[nCnt].c = c, edge[nCnt].next = pHead[u]; pHead[u] = nCnt;
edge[++nCnt].v = u; edge[nCnt].c = , edge[nCnt].next = pHead[v]; pHead[v] = nCnt;
}
int SAP (int pStart, int pEnd, int N) {
int numh[INF], h[INF], curEdge[INF], pre[INF];
int cur_flow, flow_ans = , u, neck, i, tmp;
ms (h, ); ms (numh, ); ms (pre, -);
for (i = ; i <= N; i++) curEdge[i] = pHead[i];
numh[] = N;
u = pStart;
while (h[pStart] <= N) {
if (u == pEnd) {
cur_flow = 1e9;
for (i = pStart; i != pEnd; i = edge[curEdge[i]].v)
if (cur_flow > edge[curEdge[i]].c) neck = i, cur_flow = edge[curEdge[i]].c;
for (i = pStart; i != pEnd; i = edge[curEdge[i]].v) {
tmp = curEdge[i];
edge[tmp].c -= cur_flow, edge[tmp ^ ].c += cur_flow;
}
flow_ans += cur_flow;
u = neck;
}
for ( i = curEdge[u]; i != ; i = edge[i].next)
if (edge[i].c && h[u] == h[edge[i].v] + ) break;
if (i != ) {
curEdge[u] = i, pre[edge[i].v] = u;
u = edge[i].v;
}
else {
if ( == --numh[h[u]]) continue;
curEdge[u] = pHead[u];
for (tmp = N, i = pHead[u]; i != ; i = edge[i].next)
if (edge[i].c) tmp = min (tmp, h[edge[i].v]);
h[u] = tmp + ;
++numh[h[u]];
if (u != pStart) u = pre[u];
}
}
return flow_ans;
}
long long m, n, x, y,sum,c;
int in[INF], out[INF];
bool check (long long tem) {
nCnt = ;
SS = * n + , ST = * n + ;
memset (pHead, , sizeof pHead);
for (int i = ; i <= n; i++) {
if(out[i]) addEdge (SS, i, out[i]);
for (int j =; j <= n; j++)
if (G[i][j] <= tem&&G[i][j]!=-)
addEdge (i, j+n, );
}
for (int i = ; i <= n; i++)
if(in[i])addEdge (i + n, ST, in[i]);
int ans = SAP (SS, ST, ST);
if (ans == sum) return ;
return ;
}
int main() {
/*
建图,前向星存边，表头在pHead[],边计数 nCnt.
SS,ST分别为源点和汇点
*/
ms (G, -);
cin>>n>>m;
for (int i = ; i <= n; i++) {
cin>>out[i]>>in[i];
sum += out[i];
}
long long l = 0x7fffffffffffffff, r = ;
for (int i = ; i <= n; i++) G[i][i] = ;
for (int i = ; i <= m; i++) {
cin>>x>>y>>c;
if(G[x][y]>) G[x][y] = G[y][x] = min(c,G[x][y]);
else
G[x][y]=G[y][x]=c;
l = min (l, c), r = max (r, c);
}
for (int t = ; t <= n; t++)
for (int i = ; i <= n; i++)
for (int j = ; j <= n; j++) {
if (G[i][t] == - || G[t][j] == -) continue;
if (G[i][j] == - || G[i][j] > G[i][t] + G[t][j])
G[i][j] = G[i][t] + G[t][j], l = min (l, G[i][j]), r = max (r, G[i][j]);
}
long long last = -,mid;
while (l <= r) {
mid = (l + r) >> ;
if (check (mid) ) {
last = mid;
r = mid - ;
}
else l = mid + ;
}
cout<<last;
return ;
}