问题描述

Joe 觉得云朵很美，决定去山上的商店买一些云朵。商店里有 n 朵云，云朵被编号为 $1， 2，…...，n$，并且每朵云都有一个价值。但是商店老板跟他说，一些云朵要搭配来买才好， 所以买一朵云则与这朵云有搭配的云都要买。 但是 Joe 的钱有限，所以他希望买的价值越多越好。

格式

输入

第 1 行 $n，m，w$，表示 $n$ 朵云，$m$ 个搭配，Joe 有 $w$ 的钱。 第 $2\sim n+1$ 行，每行 $c_i，d_i$ 表示 i 朵云的价钱和价值。 第 $n+2\sim n+1+m$ 行，每行 $u_i，v_i$，表示买 $u_i$ 就必须买 $v_i$，同理，如果买 $v_i$ 就必须买 $u_i$。

输出

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

样例

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

1

提示

数据范围 :

• 30%的数据保证：n<=100
• 50%的数据保证：n<=1,000；m<=100；w<=1,000
• 100%的数据保证：n<=10,000；0<=m<=5000；w<=10,000