题目描述

小A是一个电影迷，他收集了上百部的电影，打算从中挑出若干部在假期看完。他根据自己的口味和网上的介绍，对每部电影 $X$ 都打了一个分数 $v_X$，表示自己喜欢的程度。这个分数的范围在 $-1000$ 至 $1000$ 之间，越大表示越喜欢。小A每看一部电影 $X$，他的体验值就会加上 $v_X$。

另外，因为某些电影是组成一个系列的，比如著名的《终结者》系列、《黑客帝国》系列等等，如果小A只看了前一部而没有看后一部的话，他就会觉得不是很爽。准确来讲，对于任意两部不同的电影 $X,Y$，他们可能存在一个依赖值 $d_{X,Y}$，表示如果小A看了 $X$ 但是没看 $Y$，他的体验值就会减少 $d_{X,Y}$。（注意与观看的顺序无关，只要两部都看过，就不会减少体验值）

现在他要选出若干电影来看，使得得到的总的体验值最大。如果他无法得到正的体验值，就输出 $0$。

输入格式

输入的第一行是两个整数：电影总数 $N$ 和依赖关系数目 $M$。第二行包含用空格隔开的 $N$ 个数，表示对每部电影的打分。接下来 $M$ 行，每行包含三个整数 $X,Y,d_{X,Y}$，表示一个依赖关系。每个有序对 $(X,Y)$ 最多出现一次。$\pod{1\le X,Y\le N}$

输出格式

输出一个整数，表示小A能得到的最大体验值。

2 2
100 -50
1 2 49
2 1 10

51

提示

如果小A只看电影 $1$，体验值为 $100-49=51$。如果只看电影2，体验值为 $-50-10=-60$。如果两部都看，体验值为 $100+(-50)=50$。所以应该只看电影 $1$。

数据规模与约定

对于 $20\%$ 的数据，$1\le N\le 15$。

对于 $100\%$ 的数据，$1\le N\le 100,-1000\le v_X \le 1000,0<d_{X,Y}\le 1000$

每个测试点时限1秒