P3872 [TJOI2010] 电影迷

小A是一个电影迷，他收集了上百部的电影，打算从中挑出若干部在假期看完。他根据自己的口味和网上的介绍，对每部电影X都打了一个分数vX，表示自己喜欢的程度。这个分数的范围在-1000至1000之间，越大表示越喜欢。小A每看一部电影X，他的体验值就会加上vX。 另外，因为某些电影是组成一个系列的，比如著名的《终结者》系列、《黑客帝国》系列等等，如果小A只看了前一部而没有看后一部的话，他就会觉得不是很爽。准确来讲，对于任意两部不同的电影X,Y，他们可能存在一个依赖值dXY，表示如果小A看了X但是没看Y，他的体验值就会减少dXY。（注意与观看的顺序无关，只要两部都看过，就不会减少体验值） 现在他要选出若干电影来看，使得得到的总的体验值最大。如果他无法得到正的体验值，就输出0。

无

无

如果小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秒