题目描述

商场正在举办限时特卖活动，共有 $n$ 件商品，编号为 $1,2,3,\ldots,n$，每件商品都有一个价格和一个吸引力值。商场规定了一些搭配规则：某些商品必须成套购买，即如果你决定购买其中一件，那么与之搭配的其他商品也必须一并购入（搭配关系是双向的）。

你的预算是 $w$ 元，希望在不超过预算的前提下，买到吸引力总和最大的商品组合。请问最大的吸引力总和是多少？

输入格式

第一行三个整数 $n, m, w$，分别表示商品数量、搭配关系组数和预算金额。

接下来 $n$ 行，每行两个整数 $c_i, d_i$，分别表示第 $i$ 件商品的价格和吸引力值。

再接下来 $m$ 行，每行两个整数 $u_i, v_i$，表示第 $u_i$ 件商品和第 $v_i$ 件商品必须成套购买（即购买其中一件就必须购买另一件）。

输出格式

一行一个整数，表示在不超过预算的前提下可以获取的最大吸引力总和。

样例

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

1

提示

数据规模与约定

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