聪明的推销员

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 salenet.in 输出文件 salenet.out

题目描述

某商品推销员到某小区推销产品,产品推销除了商品质量好之外,还需要客户能影响和带动身边信赖他的人也购买,如果A购买了产品,那么信赖A的B就有可能也购买,那么信赖B的C就也可能成为潜在客户,依据这种信赖关系,就可能构成一个庞大的潜在客户网。聪明的推销员经过细心调查整理了这个小区里N个人的信赖关系,并且用1~N给这N个人编号。另外,这N个人中有P个潜在客户可能会被推销员直接说服购买产品,细心的推销员还估算了说服每个人具体需要花费的时间,那么请你帮推销员计算一下他最少需要花费多长时间来建立起这N个人的潜在客户网?如果不能把这N个人全部纳入潜在客户网,输出不能被纳入网络的人的编号。注意,信赖关系不一定是相互的啊!

【输人格式】

输入文件第一行只有一个整数n(n<=3000)。

    第二行是整数p。表示能被说服的人数,1pn

    接下来的p行,每行有两个整数,第一个数是一个能被说服的人的编号,第二个数表示他被说服需要花费的时间。这个数不超过20000个时间单位。

紧跟着一行只有一个整数r1r8000。然后r行,每行两个正整数,表示数对(A, B),B信赖A

【输出格式】

如果可以把N个人全部纳入潜在客户网,第一行输出YES,并在第二行输出所需要花费的最少说服时间。否则输出NO,并在第二行输出不能纳入网络的人编号中,编号最小的。

【输入样例】

Example1:

3

2

1 10

2 100

2

1 3

2 3

 

Example2:

4

2

1 100

4 200

2

1 2

3 4

【输样例】

Example1:

YES

110

Example2:

NO

3

数据规模

对于30%的输入数据有n<=10。

对于100%的输入数据有n<=3000。