小明设计了很多排爆机器人。但是机器人们都认为自己是最强的，于是，一场battle开始了，

排爆机器人们都想知道谁是最勇敢的，于是它们比赛搬运易燃易爆物品。

它们到了一个仓库，里面有n个物品，每个物品都有一个价值Pi和重量Wi，但是有些物品放在一起会爆炸，并且爆炸具有传递性（A和B会产生爆炸、B和C会爆炸则A和C会爆炸）。机器人们想知道在自己的能力范围Wmax内，它们最多可以拿多少价值的物品。

你能帮助它们吗？

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

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

再接下来k行，每行2个数字a，b表示a和b会发生爆炸

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