题目描述

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

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

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

输入格式

输入的第一行是两个整数：电影总数N和依赖关系数目M。第二行包含用空格隔开的N个数，表示对每部电影的打分。接下来M行，每行包含三个整数X, Y, dXY，表示一个依赖关系。每个有序对(X,Y)最多出现一次。(1 ≤ X,Y ≤ 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 ≤ N ≤ 15

对于100%的数据，1 ≤ N ≤ 100, -1000 ≤ vX ≤ 1000, 0 < dXY ≤ 1000

每个测试点时限1秒