409676: GYM103677 M Grape Juice Country

Grape Juice Country is one of the world's great destinations, especially for lovers of wine grape juice, fantastic food, and beautiful views. However, the $$$N$$$ ($$$1 \leq N \leq 1000$$$) vineyards of the country (conveniently numbered from $$$1$$$ to $$$N$$$) have recently been getting ransacked by thieves! The government has decided to hire Red (Grape) and Green (Grape) armed guards to patrol the $$$M$$$ ($$$1 \leq M \leq 1000$$$) directed roads (conveniently numbered from $$$1$$$ to $$$M$$$) connecting the vineyards. Each guard is stationed at a vineyard, but Red and Green guards perform different duties. While Red Guards protect all roads that are directed out of the vineyard they are stationed at, Green Guards protect all roads that are directed into the vineyard they are stationed at. A road is considered "safe" if at least one guard of either type is protecting it. The loss of stolen goods avoided by keeping road $$$i$$$ safe is $$$s_i$$$. Both types of guards are obviously not free to hire, with Red Guards and Green Guards costing $$$r_i$$$ and $$$g_i$$$, respectively, to station at vineyard $$$i$$$. The government would like to maximize the value of saved goods minus the cost of hiring guards to protect roads. Can you help as their (definitely not hungover) domestic affairs intern?

The first line of input contains two integers $$$N$$$ and $$$M$$$ as described above. The next line of input has $$$N$$$ space-separated integers $$$r_i$$$, the the cost of a Red Guard stationed on vineyard $$$i$$$. The next line of input has $$$N$$$ space-separated integers $$$g_i$$$, the the cost of a Green Guard stationed on vineyard $$$i$$$. The next $$$M$$$ lines describe the roads with three integers $$$u_i, v_i, s_i$$$. Road $$$i$$$ saves $$$s_i$$$ in cost of stolen goods and goes from vineyard $$$u_i$$$ to vineyard $$$v_i$$$ ($$$1 \leq u_i, v_i \leq N$$$). All $$$s_i, r_i, g_i$$$ are positive integers at most $$$10^9$$$ in value.

Print a single integer representing the maximal value of saved goods minus the cost of hiring guards to protect roads.

2 1
1 2
3 4
1 2 5

4

4 5
7 10 1 7
7 4 4 1
1 3 8
4 1 3
1 3 5
3 1 7
4 3 1

16