Description

Xiao A is a movie buff. He has collected hundreds of movies and plans to pick some to watch during the holidays. Based on his taste and online information, he assigned to each movie $X$ a score $v_X$ indicating how much he likes it. The score range is from $-1000$ to $1000$, and a larger score means he likes it more. Each time Xiao A watches a movie $X$, his experience increases by $v_X$.

In addition, because some movies belong to the same series (for example, the famous Terminator series, The Matrix series, etc.), if Xiao A watches an earlier one but not a later one, he will feel uncomfortable. More precisely, for any two distinct movies $X, Y$, there may be a dependency value $d_{X,Y}$, meaning that if Xiao A watches $X$ but not $Y$, his experience will decrease by $d_{X,Y}$. (Note that the viewing order does not matter; as long as both are watched, there is no penalty.)

Now he wants to select some movies to watch to maximize the total experience. If he cannot obtain a positive experience, output $0$.

Input Format

• The first line contains two integers: the total number of movies $N$ and the number of dependency relations $M$.
• The second line contains $N$ space-separated numbers, the scores for each movie.
• Each of the next $M$ lines contains three integers $X, Y, d_{X,Y}$, representing a dependency relation.
• Each ordered pair $(X, Y)$ appears at most once. $1 \le X, Y \le N$.

Output Format

Output one integer, the maximum experience Xiao A can obtain.

2 2
100 -50
1 2 49
2 1 10

51

Hint

If Xiao A only watches movie $1$, the experience is $100 - 49 = 51$. If he only watches movie $2$, the experience is $-50 - 10 = -60$. If he watches both, the experience is $100 + (-50) = 50$. Therefore, he should only watch movie $1$.

Constraints:

• For $20\%$ of the testdata, $1 \le N \le 15$.
• For $100\%$ of the testdata, $1 \le N \le 100$, $-1000 \le v_X \le 1000$, $0 < d_{X,Y} \le 1000$.
• Time limit per test point is 1 second.

Translated by ChatGPT 5