Maximum Movie Experience

Little A is a movie fan who has collected hundreds of movies. He rates each movie \(X\) with a score \(v_X\) in the range \(-1000\) to \(1000\), where a larger score means he likes it more. When he watches a movie \(X\), his experience increases by \(v_X\).

However, some movies are part of a series. For any two different movies \(X\) and \(Y\), there might be a dependency penalty \(d_{X,Y}\). This penalty applies if Little A watches movie \(X\) but does not watch movie \(Y\) (the order does not matter, as long as both are watched, no penalty is imposed).

Your task is to help Little A choose a subset of movies such that his total experience is maximized. The total experience is defined as the sum of the selected movies' scores minus the sum of all incurred dependency penalties. If the maximum total experience is not positive, output \(0\).

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \le n \le 1000\), \(0 \le m \le 10000\)), representing the number of movies and the number of dependency constraints.

The second line contains \(n\) integers \(v_1, v_2, \dots, v_n\) (\(-1000 \le v_i \le 1000\)), where \(v_i\) is the score for the \(i\)-th movie.

Each of the next \(m\) lines contains three integers \(X\), \(Y\), and \(d_{X,Y}\) (\(1 \le X, Y \le n\), \(X \neq Y\), \(1 \le d_{X,Y} \le 1000\)), meaning that if movie \(X\) is selected and movie \(Y\) is not, Little A's experience will decrease by \(d_{X,Y}\).

outputFormat

Output a single integer, the maximum total experience Little A can achieve. If he cannot get a positive experience, output \(0\).

sample

3 3
5 -2 10
1 2 3
2 3 4
1 3 2

13