题目描述

新学期开学，学校周边的文具店推出了新款盲盒笔套装。店里有 n 款不同的盲盒笔，每款都有对应的售价和收藏价值，老板给这些笔编了号 1,2,3,...,n。不过这家店有个特别的规则：部分盲盒笔属于「系列款」，必须整套购买 —— 也就是说，如果你想买某一款系列笔，就必须把和它同系列的所有笔都买下来。你带了固定数额的零花钱，想在预算范围内买到收藏价值总和最大的盲盒笔，请问最多能获得多少价值？

输入格式

第一行输入三个整数 n,m,w，分别表示盲盒笔的总数、「系列款」的关联组数、你拥有的零花钱总数。

第二行至第 n+1 行，每行两个整数 ci​,di​，表示第 i 款盲盒笔的售价和收藏价值。

第 n+2 行至第 n+1+m 行，每行两个整数 ui​,vi​，表示第 ui​ 款和第 vi​ 款盲盒笔属于同一个系列（买其中一款就必须买另一款）。

输出格式

一行，输出你能获得的最大收藏价值。

输入输出样例 #1

输入 #1

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

输出 #1

1

说明/提示

• 对于 $30\%$ 的数据，满足 $1 \le n \le 100$；
• 对于 $50\%$ 的数据，满足 $1 \le n, w \le 10^3$，$1 \le m \le 100$；
• 对于 $100\%$ 的数据，满足 $1 \le n, w \le 10^4$，$0 \le m \le 5 \times 10^3$。