1723 - Stations
Time Limit : 1 Second
Memory Limit : 256 MB
Submission: 7
Solved: 2
- Description
After stuck in a traffic jam millions of times in Wuhan, zf decided to re-planning bus lines.
First there are N alternative stations determined by the experts, each station needs maintenance costs Pi,
After investigation he found that there are M user groups, often going from the Ai station to the Bi station, can provide Ci earnings.
Now, boss zf would like to know, the maximum profit is how much? (the sum of the earnings minus the sum of the costs)
- Input
There are multiple sets of data for this question.
Each set of data T <= 10
The first row of each set of data is two positive integers N and M.
The second line has N integers(P1, P2, ..., PN)describing the cost of building each station.
The next M rows, Ai, Bi and Ci in the (i + 2) th row describe the information of the i-th user group.
The meaning of all variables can be found in the description.
- Output
Outputs an integer for each set of data, indicating the maximum profit that the company can get.
- sample input
-
5 5 1 2 3 4 5 1 2 3 2 3 4 1 3 3 1 4 2 4 5 3
- sample output
-
4
- hint
- source
- pengyanyu