3117 問題 Q: 搭配購買(buy)
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 81 解決: 36
題目描述
Joe覺得云朵很美,決定去山上的商店買一些云朵。商店里有n朵云,云朵被編號(hào)為1,2,…,n,并且每朵云都有一個(gè)價(jià)值。但是商店老板跟他說,一些云朵要搭配來買才好,所以買一朵云則與這朵云有搭配的云都要買。
但是Joe的錢有限,所以他希望買的價(jià)值越多越好。
輸入
第1行n,m,w,表示n朵云,m個(gè)搭配,Joe有w的錢。
第2~n+1行,每行ci,di表示i朵云的價(jià)錢和價(jià)值。
第n+2~n+1+m行,每行ui,vi,表示買ui就必須買vi,同理,如果買vi就必須買ui。
樣例輸入
5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2
提示
【數(shù)據(jù)范圍】
30%的數(shù)據(jù)保證:n≤100;
50%的數(shù)據(jù)保證:n≤1,000;m≤100;w≤1,000;
100%的數(shù)據(jù)保證:n≤10,000;0≤m≤5000;w≤10,000。