409676: GYM103677 M Grape Juice Country

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

M. Grape Juice Countrytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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?

Input

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.

Output

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

ExamplesInput
2 1
1 2
3 4
1 2 5
Output
4
Input
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
Output
16

加入题单

上一题 下一题 算法标签: