1484.
最勇敢的机器人
时间限制 1000 ms
内存限制 128 MB
机器人们都想知道谁是最勇敢的,于是它们比赛搬运一些物品。
它们到了一个仓库,里面有n个物品,每个物品都有一个价值Pi和重量Wi,但是有些物品放在一起会爆炸,并且爆炸具有传递性。(a和b会爆炸、b和c会爆炸则a和c会爆炸)
机器人们可不想因此损失自己好不容易从Wind那里敲诈来的装备,于是它们想知道在能力范围内,它们最多可以拿多少价值的物品。
你能帮助它们吗?
输入数据
输出数据
样例输入
复制
3 10 1
100 1
200 5
10 5
1 2
· · \n
· \n
· \n
· \n
· \n