New technology is impacting the mobile communications market, presenting both opportunities and challenges for major operators. On the eve of a fierce battle in next-generation communication technology, the CS&T communications company under the THU Group needs to perform extensive preparatory work. For site selection alone, it must complete preliminary market research, site surveying, and optimization projects.

Following preliminary market research and site surveying, the company has identified a total of $N$ potential locations for communication signal relay stations. Due to differences in the geographical locations of these sites, the costs of building relay stations vary. Fortunately, these costs are known after the preliminary survey: the cost to build the $i$-th relay station is $P_i$ ($1 \le i \le N$).

Additionally, the company has surveyed all potential user groups, totaling $M$. Information about the $i$-th user group is summarized by $A_i$, $B_i$, and $C_i$: these users will communicate using relay station $A_i$ and relay station $B_i$, and the company can earn a profit of $C_i$ ($1 \le i \le M$, $1 \le A_i, B_i \le N$).

The CS&T company of the THU Group can choose to build some relay stations (incurring costs) to provide services to some user groups and earn revenue (the sum of profits). How should the company choose which relay stations to build to maximize its net profit? (Net profit = Sum of revenue – Sum of construction costs)

Input

The first line of the input file contains two positive integers $N$ and $M$.

The second line contains $N$ integers describing the construction cost of each communication relay station, which are $P_1, P_2, \dots, P_N$ in order.

The following $M$ lines each contain three integers $A_i$, $B_i$, and $C_i$, describing the information for the $i$-th user group.

The meanings of all variables can be found in the problem description.

Output

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

Examples

Input 1

5 5 
1 2 3 4 5 
1 2 3 
2 3 4 
1 3 3 
1 4 2 
4 5 3

Output 1

4

Note

Choosing to build relay stations 1, 2, and 3 requires an investment cost of 6 and yields a revenue of 10, resulting in a maximum profit of 4.

Subtasks

This problem has no partial points. Your program's output must be exactly consistent with our answer to receive full marks; otherwise, it will receive no points.

Constraints

For 80% of the data: $N \le 200$, $M \le 1\,000$.

For 100% of the data: $N \le 5\,000$, $M \le 50\,000$, $0 \le C_i \le 100$, $0 \le P_i \le 100$.