问题1650--双核CPU

1650: 双核CPU

时间限制: 1 Sec  内存限制: 128 MB
提交: 33  解决: 15
[提交] [状态] [讨论版] [命题人:]

题目描述

BSNY有一台双核CPU的电脑,作为电脑发烧友的他,当然希望两个CPU都能充分利用。现在他有n个进程要跑,每个进程在不同CPU上运行的代价不一样,对于第i个任务,在两个CPU上跑的代价分别为ai, biBSNY希望消耗总的代价最小。

罗老师认为这个问题太简单了,BSNY肯定会让每个任务都去代价小的CPU上运行,于是他加了限制条件:给定m个限制,格式为x y z,表示如果第x个任务和第y个任务不在同一个CPU上运行,需要额外消耗代价为z

这让BSNY着实有点困扰,到底怎样分配任务使用的CPU,可以使代价最小,求最小代价?

输入

第一行输入n, m

接下来n行,每行两个整数ai, bi

接下来m行,每行三个整数x, y, z

输出

输出最小代价

样例输入 Copy

3 1
1 10
2 10
10 3
2 3 1000

样例输出 Copy

13

提示

【样例说明】

任务123都在CPU1上运行最好,代价为13

如果任务12CPU1,任务3CPU2,那么代价为1+2+3+1000=1006

【数据规模和约定】

40%数据    1<=n<=200    0<=m<=2000

100%数据   1<=n<=20000  0<=m<=200000  0<=ai, bi, z<=10000

来源/分类