409323: GYM103485 E Protecting Roads

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

Description

E. Protecting Roadstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

The University of São Paulo is famous for having many subsidiaries, most famously in São Carlos. The university, looking for a global expansion, has plans to create a subsidiary in Egypt. In typical USP fashion, this new university can be seen as a set of $$$n$$$ roundabouts (numbered from $$$1$$$ to $$$n$$$) connected by $$$m$$$ directed roads.

The egyptian government, wanting to incentivize the protection of its citizens, will pay $$$e_i$$$ egyptian pounds to the university for every road $$$i$$$ it protects.

To protect a road, the university needs to hire guards and place them at roundabouts. Guards in Egypt are really specialized: there are two types of guards, blue and red guards.

Blue guards, when standing at roundabout $$$i$$$ will cost $$$b_i$$$ and will be able to protect all roads $$$ij$$$ (that is, a directed road from $$$i$$$ to $$$j$$$).

Red guards, when standing at roundabout $$$i$$$ will cost $$$r_i$$$ and will be able to protect all roads $$$ji$$$ (that is, a directed road from $$$j$$$ to $$$i$$$).

What is the maximum possible profit the university can have with an unlimited supply of blue and red guards?

Input

The first line contains two numbers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^3,0 \leq m \leq 10^3$$$) - the number of roundabouts and roads in the university, respectively.

The next line has $$$n$$$ numbers $$$b_1, b_2, ..., b_n$$$ ($$$1 \leq b_i \leq 10^9$$$) - the cost of a blue guard on each roundabout.

The next line has $$$n$$$ numbers $$$r_1, r_2, ..., r_n$$$ ($$$1 \leq r_i \leq 10^9$$$) - the cost of a red guard on each roundabout.

The next $$$m$$$ lines describe the roads. The $$$i$$$-th line contains three integers $$$v_i, u_i, e_i$$$ ($$$1 \leq v_i, u_i \leq n$$$, $$$1 \leq e_i \leq 10^9$$$), which means that there is a directed road from $$$v_i$$$ to $$$u_i$$$ that is worth $$$e_i$$$ when protected.

Note that the graph defined by roundabouts and roads can have multiple edges, self-loops and is not necessarily connected.

Output

Print one integer - the maximum possible profit the university can have.

ExamplesInput
3 3
6 5 5
7 3 6
1 2 2
2 3 2
3 2 9
Output
8
Input
2 1
1 3
2 2
1 2 5
Output
4
Input
1 2
2
3
1 1 2
1 1 1
Output
1

加入题单

上一题 下一题 算法标签: