409323: GYM103485 E Protecting Roads

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?

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.

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

3 3
6 5 5
7 3 6
1 2 2
2 3 2
3 2 9

8

2 1
1 3
2 2
1 2 5

4

1 2
2
3
1 1 2
1 1 1

1