1252

1252. 搭配购买

题目

Joe觉得云朵很美，决定去山上的商店买一些云朵。

商店里有 $n$ 朵云，云朵被编号为 $1,2,…,n$，并且每朵云都有一个价值。

但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。

但是Joe的钱有限，所以他希望买的价值越多越好。

输入格式

第 $1$ 行包含三个整数 $n，m，w$，表示有 $n$ 朵云，$m$ 个搭配，Joe有 $w$ 的钱。

第 $2 \sim n+1$行，每行两个整数 $c_i，d_i$ 表示 $i$ 朵云的价钱和价值。

第 $n+2 \sim n+1+m$ 行，每行两个整数 $u_i，v_i$，表示买 $u_i$ 就必须买 $v_i$，同理，如果买 $v_i$ 就必须买 $u_i$。

输出格式

一行，表示可以获得的最大价值。

数据范围

$1 \le n \le 10000$,

$0 \le m \le 5000$,

$1 \le w \le 10000$,

$1 \le c_i \le 5000$,

$1 \le d_i \le 100$,

$1 \le u_i,v_i \le n$

输入样例：

5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2

输出样例：

1

题解