题目描述

王老师来到商店为同学们采购礼品。这家店有 $n$ 种礼品（编号是 $1 \sim n$），每种礼品只有 $1$ 件。老板为了促销，对礼品进行搭配销售，有关联性的礼品必须都要采购，比如 $1$ 号礼品和 $3$ 号礼品搭配了，$3$ 号和 $8$ 号礼品搭配了，那么王老师想要买 $1$ 号礼品的话，就需要把 $3$ 号和 $8$ 号礼品都买了。

现给定每种礼品的价钱和价值，请问在有限的钱 $w$ 的情况下，能够买到礼品的最大价值是多少？

输入格式

第一行输入三个整数 $n, m, w$，分别表示有 $n$ 种礼品，$m$ 个搭配和你现有的钱的数目。

第二行至第 $n+1$ 行，每行有两个整数 $c_i, d_i$，表示第 $i$ 种礼品的价钱和价值。

第 $n+2$ 至第 $n+1+m$ 行，每行有两个整数 $u, v$，表示 $u$ 号礼品和 $v$ 号礼品是有关联的，已经形成搭配销售的关系。

输出格式

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

样例

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

1

样例解释
关联关系形成两个连通块：$\{1,2,3,4\}$ 和 $\{5\}$。购买连通块 $\{1,2,3,4\}$ 的总价钱为 $3+3+3+5=14$，超过了 $10$，无法购买。只能购买连通块 $\{5\}$，价钱为 $10$，价值为 $1$。故最大价值为 $1$。

数据范围

• $1 \le n, w \le 10^4$
• $0 \le m \le 5 \times 10^3$
• $1 \le c_i, d_i \le 10^5$