Joe 觉得云朵很美,决定去山上的商店买一些云朵。商店里有 n 朵云,云朵被编号为 1,2,…,n , , , ,并且每朵云都有一个价值。但是商店老板跟他说,一些云朵要搭配来买才好,所以买一朵云则与这朵云有搭配的云都要买。
但是 Joe 的钱有限,所以他希望买的价值越多越好。
第 1 行 n,m,w, , , , 表示 n 朵云, m 个搭配, Joe 有 w 的钱。
第 2 ~ n+1 行,每行 c_i,d_i , 表示 i 朵云的价钱和价值。
第 n+2 ~ n+1+m 行,每行 u_i,v_i, , , 表示买 u_i 就必须买 v_i ,同理,如果买 v_i 就必须买 u_i 。
一行,表示可以获得的最大价值。
5 3 10 3 10 3 10 3 10 5 100 10 1 1 3 3 2 4 2
1
30% 的数据保证: n≤100
50% 的数据保证: n≤1,000;m≤100;w≤1,000 ; ;
100% 的数据保证: n≤10,000;0≤m≤5000;w≤10,000 ; ;