National Olympiad in Informatics, China, 2006

Day 2, Problem 1 - Maximum Profit

New technology is bombarding the mobile communications market. For major cellphone carriers, this is both an opportunity and a challenge. The THU Group's CS&T communications company is at the eve of a bloody battle in a new generation of communication technology. So much preparatory work needs to be done. For the site-selection aspect alone, they will need to complete prior market research, site investigation, optimization, and other projects.

After the market research and site investigation, the company has determined a total of N sites for relay stations of cellular signals. Due to geographical factors of these sites, establishing relay stations at different places require different principal costs. Luckily this cost data is already known after the prior market research: establishing the i-th relay station requires a principal cost of Pi (1 ≤ i ≤ N).

The company also researched the expected user base, consisting of M total customer groups. The i-th group's information can be summarized using the values Ai, Bi, and Ci. Users in this group will use relay stations Ai and Bi for communication, allowing the company to receive Ci in revenue (1 ≤ i ≤ M, 1 ≤ Ai, Bi ≤ N).

The THU Group's CS&T company can select a group of relay stations to establish (thus paying the necessary principal cost), servicing certain customer groups (thus receiving revenue). How must they select which relay stations to establish so that the company can receive the maximum possible profit? (Profit = total revenue − total principal cost)

Input Format

The first line of input contains two integers N and M.
The second line contains N integers describing the principal cost to build each relay station, respectively P1, P2, …, PN.
There will be M lines to follow. Line (i + 2) of input will contain 3 integers Ai, Bi, and Ci describing the information about the i-th customer group.

Output Format

Your program should output a single integer, representing the maximum profit that the company can obtain.

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

Explanation

By building relay stations 1, 2, and 3, the total principal cost will be 6, and the total revenue will be 10. This yields the maximum profit of 4.

Constraints

For 80% of the test cases: N ≤ 200, M ≤ 1000.
For 100% of the test cases: N ≤ 5000, M ≤ 50000, 0 ≤ Ci ≤ 100, 0 ≤ Pi ≤ 100.

All Submissions
Best Solutions


Point Value: 20 (partial)
Time Limit: 2.00s
Memory Limit: 256M
Added: Jul 23, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3