题目描述

王老师来到商店为同学们采购礼品。

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

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

输入描述

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

第二行至$n+1$行，每行有两个整数，$c$、$d$，表示第$i$种礼品的价钱和价值。（$1≤c,d≤10^5$）

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

数据范围：

$1≤n,w≤10^4,0≤m≤5 \times 10^3$。

输出描述

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

样例

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

1