题目描述

商店里有 $n$ 朵云，第 $i$ 朵云的价格为 $c_i$，价值为 $d_i$。每朵云只能购买一次。

一些云必须搭配购买：如果购买其中一朵，就必须购买与它有搭配关系的另一朵，搭配关系可以继续传递。

Joe 有 $w$ 元，请在满足所有搭配要求、总价格不超过 $w$ 的前提下，求能获得的最大价值。可以什么都不买。

输入格式

第一行三个整数 $n,m,w$。接下来 $n$ 行，每行两个整数 $c_i,d_i$。接下来 $m$ 行，每行两个整数 $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\%$ 的数据，$n\le100$。
• 对于 $50\%$ 的数据，$n\le1000$，$m\le100$，$w\le1000$。
• 对于 $100\%$ 的数据，$1\le n\le10000$，$0\le m\le5000$，$1\le w\le10000$，$1\le c_i,d_i\le10000$，$1\le u_i,v_i\le n$，$u_i\ne v_i$。