1484. 最勇敢的机器人

时间限制 1000 ms   内存限制 128 MB

机器人们都想知道谁是最勇敢的,于是它们比赛搬运一些物品。 它们到了一个仓库,里面有n个物品,每个物品都有一个价值Pi和重量Wi,但是有些物品放在一起会爆炸,并且爆炸具有传递性。(a和b会爆炸、b和c会爆炸则a和c会爆炸) 机器人们可不想因此损失自己好不容易从Wind那里敲诈来的装备,于是它们想知道在能力范围内,它们最多可以拿多少价值的物品。 你能帮助它们吗?

输入数据

每组测试数据
第1行为n,Wmax,k(0< =n,Wmax,k< =1000)
接下来n行,为每个物品的Pi,Wi(0< =Pi< =1000,1< =Wi< =10,均为整数)
再接下来k行,每行2个数字a,b表示a和b会发生爆炸

输出数据

对每组数据输出1行
为最大可能价值

样例输入

复制
3 10 1
100 1
200 5
10 5
1 2
 ·  · \n
   · \n
   · \n
  · \n
 · \n

样例输出

复制
210
   \n

提交

请先 登录

Source

Wind

© 2024 FAQs Contact About