Itsy Bitsy Spider
The itsy bitsy spider, climbed up the water spout,
down came the rain, and washed the spider out.
Itsy knew it wouldn't be long, before she rose again,
and so she tried to eat big flies, before she hit the drain.
Itsy could only follow the flow, down through the pipe,
with flies in her belly, and sunshine in her sights.
And so when the sun came out, and dried up all the rain,
the itsy bitsy spider, new heights she did attain.
The itsy bitsy spider is about to be washed down the pipe system, and knows this is about to occur.
She would like to get a head start on climbing the pipes a second time, by ensuring she eats as many flies as possible on her path down the pipe system.
The pipe system is a series of connector nodes, connected via pipes. Each of these pipes will have water flowing from a higher connector node to a lower connecter node, unless they are at an equal height in which case no water shall flow.
Each pipe also contains an integer number of flies, which Itsy can eat on her way down.
Please print the maximum number of flies that Itsy can eat, travelling from one connector node to another, while only following the flow of water.
Input
Input will begin with two space-separated integers, and , the number of connector nodes and pipes respectively.
lines then follow, each containing two space-separated floating point numbers, representing the and position of the connector nodes. Positive is further right, and positive is further up.
lines then follow, containing three space-separated integers. The first two integers are the start and end indexes of a pipe, while the third integer represents how many flies are in that pipe. For example, 4 1 10
means there are 10 spiders in the pipe connecting the 1st and 4th connector nodes.
Output
Output should contain a single integer, representing the maximum amount of flies the itsy bitsy spider can eat.
Constraints
Example 1
For Input
6 7
12.0 11.2
9.0 11.2
10.0 8.5
9.5 6.9
7.3 4.6
12.0 5.3
1 3 12
3 2 8
3 4 7
4 5 9
6 4 11
1 6 25
1 2 100
Output should read 30
, which can be achieved by taking the path from 1-3-4-6
.
Example 2
For Input
5 4
5 1
4 2
3 3
2 4
1 5
1 2 5
3 4 4
5 4 4
3 5 3
Output should read 8
, taking the path from 5-4-3
.
Comments