问题 22653 --机器人比赛

22653: 机器人比赛

时间限制: 1 Sec  内存限制: 128 MB
提交: 68  解决: 23
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][172kb]

题目描述

Wind设计了很多机器人。但是它们都认为自己是最强的,于是,一场比赛开始了~

机器人们都想知道谁是最勇敢的,于是它们比赛搬运一些物品。

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

你能帮助它们吗?

输入

每组测试数据第1行为n,Wmax,k(0<=n,Wmax,k<=1000)

接下来n行,为每个物品的Pi,Wi(0<=Pi<=1000,1<=Wi<=10,均为整数)

再接下来k行,每行2个数字ab表示ab会发生爆炸

输出

只有一个整数,表示最大可能的价值。

样例输入

3 10 1
100 1
200 5
10 5
1 2

样例输出

210

提示

来源

[提交][状态]