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 contains 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

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 \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.