|
|
|
|
背景 Background |
|
|
|
Wind设计了很多机器人。但是它们都认为自己是最强的，于是，一场比赛开始了~
|
|
|
|
|
|
|
|
描述 Description |
|
|
|
机器人们都想知道谁是最勇敢的，于是它们比赛搬运一些物品。
它们到了一个仓库，里面有n个物品，每个物品都有一个价值Pi和重量Wi，但是有些物品放在一起会爆炸，并且爆炸具有传递性。（a和b会爆炸、b和c会爆炸则a和c会爆炸）
机器人们可不想因此损失自己好不容易从Wind那里敲诈来的装备，于是它们想知道在能力范围内，它们最多可以拿多少价值的物品。
你能帮助它们吗？
|
|
|
|
|
|
|
|
输入格式 Input Format |
|
| |
每组测试数据
第1行为n,Wmax,k(0<=n,Wmax,k<=1000)
接下来n行，为每个物品的Pi,Wi(0<=Pi<=1000,1<=Wi<=10,均为整数)
再接下来k行，每行2个数字a,b表示a和b会发生爆炸
|
|
|
|
|
|
|
|
输出格式 Output Format |
|
| |
对每组数据输出1行
为最大可能价值 |
|
|
|
|
|
|
|
时间限制 Time Limitation |
|
|
|
每个测试点1s |
|
|
|
|
|
|
|
|
Flag |
|
题号 |
P1250 |
|
其它 |
通过 |
1人 |
提交 |
5次 |
通过率 |
20% |
难度 |
3 |
|
|
|
|
|
|
