Preparing NOJ

通讯站建设

1000ms 65536K

Description:

YM同学调查得知:新的技术正冲击着手机通讯市场,南京移动公司准备新建一些通讯站,它们一共得到N个可以作为通讯站的数据,其中中建立第i个通讯站需要成本Pi。另外,公司得到M条用户群信息,第i个用户群会使用通讯站AiBi进行通信,公司将获利Ci1≤i≤M, 1≤Ai, Bi≤N)。公司选择建立一些通讯站(投入成本),为一些用户群提供服务并获得收益(获益之和)。那么如何选择最终建立的中转站才能让公司的净获利最大呢?(净获利 = 获益之和 - 投入成本之和)

Input:

多组输入数据。

每组数据第一行有2个正整数NM。第二行中有N个整数描述每一个通讯中转站的建立成本,依次为P1, P2, …, PN 。接下来M行,第(i + 2)行的三个数Ai, BiCi描述第i个用户群的信息。(N≤12M≤500≤Ci≤1000≤Pi≤100。)

Output:

每组数据输出一个整数,表示公司可以得到的最大净获利。

Sample Input:

5 5
1 2 3 4 5
1 2 3
2 3 4
1 3 3
1 4 2
4 5 3

Sample Output:

4

Note:

样例说明:选择建立123号中转站,则需要投入成本6,获利为10,因此得到最大收益4

 

本题由旧版NOJ导入,来源:ym

Info

NOJ

Provider NOJ

Code NOJ1656

Tags

Submitted 1

Passed 1

AC Rate 100%

Date 04/20/2019 10:03:10

Related

Nothing Yet