Background

螃蟹在剥我的壳，笔记本在写我，漫天的我落在枫叶上雪花上。而你在想我。

Description

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

Format

Input

输入有多组数据，每组数据第 1 行、m、w，表示 n 朵云，m 个搭配，Joe 有 w 的钱。
第 2 至 n+1 行，每行 ci、di 表示 i 朵云的价钱和价值。
第 n+2 至 n+1+m 行，每行 ui、vi 表示买 ui 就必须买 vi，同理，如果买 vi 就必须买 ui。

Output

对于每组数据，输出一行，表示可以获得的最大价值。

Sample

Input

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

Output

1

Limitation

30%的数据满足：n<=100；
50%的数据满足：n<=1000；m<=100；w<=1000；
100%的数据满足：n<=10000；0<=m<=5000；w<=10000。
1s, 256000KiB for each test case.

Hint

Source

CDQZ TEST
《信息学奥赛一本通》 1387