Farm Shelter Assignment

There are \(n\) fields on a farm connected by \(m\) undirected roads, where each road \( (u,v,d) \) has a length \(d\). In each field, a group of cows is grazing and every field has a cowshed (barn) with a limited capacity. When a sudden heavy rain comes, every cow will try to take shelter in one of the barns. A cow moving a distance of \(1\) takes \(1\) unit of time. A cow can move from its starting field \(i\) to any other field \(j\) if the shortest distance between \(i\) and \(j\) is at most \(T\).

The input provides:

• The number of fields \(n\) and the number of roads \(m\).
• An array of \(n\) integers, where the \(i\)th integer is the number of cows initially in field \(i\).
• An array of \(n\) integers, where the \(i\)th integer is the capacity of the barn in field \(i\) (the maximum number of cows it can shelter).
• Then \(m\) lines follow, each containing three integers \(u,v,d\) meaning there is an undirected road between field \(u\) and field \(v\) with length \(d\).

The task is to determine the minimum time \(T\) so that all cows can be assigned to barns (each barn cannot exceed its capacity). In other words, find the smallest \(T\) such that it is possible to assign every cow to some barn where the shortest path from its starting field to the barn is at most \(T\).

Note: It is guaranteed that the total number of cows equals the total barn capacity, and a solution always exists for a sufficiently large \(T\).

inputFormat

The input is given in the following format:

n m
c[1] c[2] ... c[n]
p[1] p[2] ... p[n]
u1 v1 d1
u2 v2 d2
... 
um vm dm

Where:

• \(n\) is the number of fields.
• \(m\) is the number of roads.
• \(c[i]\) is the number of cows in field \(i\).
• \(p[i]\) is the capacity of the barn in field \(i\).
• Each of the next \(m\) lines contains three integers \(u, v, d\), representing an undirected road connecting fields \(u\) and \(v\) with length \(d\).

outputFormat

Output a single integer \(T\), the minimum time such that all cows can be sheltered in barns under the given constraints.

sample

3 3
4 2 1
3 3 1
1 2 1
2 3 2
1 3 4

1