NOI '06 P4 - Maximum Profit

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type
National Olympiad in Informatics, China, 2006

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 P_i (1 \le i \le 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 A_i, B_i, and C_i. Users in this group will use relay stations A_i and B_i for communication, allowing the company to receive C_i in revenue (1 \le i \le M, 1 \le A_i, B_i \le 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 Specification

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 P_1, P_2, \dots, P_N.
There will be M lines to follow. Line (i + 2) of input will contain 3 integers A_i, B_i, and C_i describing the information about the i-th customer group.

Output Specification

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



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.


For 80% of the test cases: N \le 200, M \le 1\,000.
For 100% of the test cases: N \le 5\,000, M \le 50\,000, 0 \le C_i \le 100, 0 \le P_i \le 100.

Problem translated to English by Alex.


There are no comments at the moment.