Maximum Subset Score in a Graph

Given an undirected graph with n vertices and m edges. Each vertex i has an associated weight a_i. For any subset A of {1,2,…,n}, its score is defined as follows:

1. Start with a score of 0.
2. For every vertex i in A, add a_i to the score.
3. For every edge (u, v, k) (representing an edge between vertices u and v with penalty k) such that both u and v are in A, subtract k from the score.

The goal is to find the maximum score among all possible subsets A (the empty subset is allowed with score 0). In mathematical terms, if we define an indicator variable x_i which is 1 if vertex i is chosen and 0 otherwise, the score is given by:

[ \text{Score}(A) = \sum_{i=1}^{n} a_i x_i - \sum_{(u,v,k) \text{ edge}} k, x_u x_v, ]

Note that each edge penalty is applied only once (if both endpoints are chosen).

inputFormat

The first line contains two integers n and m — the number of vertices and edges, respectively.

The second line contains n integers, where the i^th integer denotes a_i, the weight of the i^th vertex.

Each of the following m lines contains three integers u, v, and k, representing an undirected edge between vertices u and v with penalty k. The vertices are 1-indexed.

outputFormat

Output a single integer — the maximum score obtainable among all subsets of vertices.

sample

1 0
5

5