U19001.搭配购买
普及-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
Joe觉得云朵很美,决定去山上的商店买一些云朵。
商店里有 n朵云,云朵被编号为 1,2,…,n,并且每朵云都有一个价值。
但是商店老板跟他说,一些云朵要搭配来买才好,所以买一朵云则与这朵云有搭配的云都要买。
但是Joe的钱有限,所以他希望买的价值越多越好。
输入格式
第 1行包含三个整数 n,m,w,表示有 n朵云,m 个搭配,Joe有 w
的钱。
第 2∼n+1行,每行两个整数 ci,di表示 i朵云的价钱和价值。
第 n+2∼n+1+m行,每行两个整数 ui,vi,表示买 ui 就必须买 vi,同理,如果买 vi 就必须买 ui。
输出格式
一行,表示可以获得的最大价值。
输入输出样例
输入#1
5 3 10 3 10 3 10 3 10 5 100 10 1 1 3 3 2 4 2
输出#1
1
说明/提示
1≤n≤10000,
0≤m≤5000,
1≤w≤10000,
1≤ci≤5000,
1≤di≤100,
1≤ui,vi≤n