407676: GYM102870 F Flow of Orz Pandas

There are $$$n$$$ villages in a county of the Orz Pandas. The $$$i$$$-th village needs $$$w_i$$$ tons of water per day. The Orz Pandas have built $$$k$$$ water supply facilities. The $$$i$$$-th water supply facility is located at the $$$s_i$$$-th village. The water supply facilities are very powerful, so we could consider each of them able to supply infinite amount of water per day.

The Orz Pandas have built water supply pipe networks to satisify the water usage of the villages. There are $$$m$$$ water supply pipes already built. The $$$i$$$-th pipe is between the village $$$u_i$$$ and the village $$$v_i$$$. The pipes are bidirectional: if there is a pipe between $$$u_i$$$ and $$$v_i$$$, it's allowed to transfer water from $$$u_i$$$ to $$$v_i$$$, or from $$$v_i$$$ to $$$u_i$$$, through this pipe. Pipe $$$i$$$ has a parameter $$$c_i$$$. If $$$f_i$$$ tons of water are transfered through the $$$i$$$-th pipe per day, the Orz Pandas will have to pay $$$f_i^2 \times c_i$$$ dollars per day to maintain the pipe.

Please tell the Orz Pandas the minimum cost they must pay per day, to satisify the water usage of all the villages.

There is only one test case in each input file.

• The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$.
• The second line contains $$$n$$$ integers $$$w_1, w_2, \cdots, w_n$$$.
• The third line contains $$$k$$$ integers $$$s_1, s_2, \cdots, s_k$$$.
• The $$$i$$$-th of the following $$$m$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$, and $$$c_i$$$.

It's guaranteed that $$$1 \leq n \leq 50$$$, $$$0 \leq m \leq 200$$$, $$$1 \leq k, s_i, u_i, v_i \leq n$$$, and $$$0 \leq w_i, c_i \leq 1000$$$.

There may be multiple pipes connecting the same pair of villages. There may be some pipe both endings of which are the same village. There may be multiple water supply facilities in the same village.

If the water usage of all the villages can be satisified, output one line containing a decimal, which is the minimum cost. Otherwise, output one line containing $$$-1$$$. Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-9}$$$.

7 5 2
0 0 0 0 1 1 0
1 3
1 2 1
3 4 2
4 2 1
2 5 2
4 6 1

5.75

7 5 2
0 0 0 0 1 1 1
1 3
1 2 1
3 4 2
4 2 1
2 5 2
4 6 1

-1

For the first sample, the optimal solution is:

• Transfer $$$1.25$$$ tons of water from village $$$1$$$ to village $$$2$$$ per day, costing $$$1.25^2 \times 1 = 1.5625$$$ dollars per day.
• Transfer $$$0.75$$$ tons of water from village $$$3$$$ to village $$$4$$$ per day, costing $$$0.75^2 \times 2 = 1.125$$$ dollars per day.
• Transfer $$$0.25$$$ tons of water from village $$$2$$$ to village $$$4$$$ per day, costing $$$0.25^2 \times 1 = 0.0625$$$ dollars per day.
• Transfer $$$1$$$ ton of water from village $$$2$$$ to village $$$5$$$ per day, costing $$$1^2 \times 2 = 2$$$ dollars per day.
• Transfer $$$1$$$ ton of water from village $$$4$$$ to village $$$6$$$ per day, costing $$$1^2 \times 1 = 1$$$ dollars per day.

For the second sample, it's impossible to satisify village $$$7$$$ since there is no way to connect it to a water supply facility.