Description

明天就是坤坤日了，会玩电脑的小黑子在忙碌的打球之余挖空心思想着该送什么奇葩礼物来表达自己的心意呢？听说在某个平台上有卖比普通汽水的汽多10倍汽的汽水（喷射战士），小黑子们决定一同去康康这种“神奇”的汽水，这个店里有n瓶这样的汽水，汽水已经被老板编号为 1,2,3,...,，并且每瓶汽水都有一个价值，但是商店的老板是个奇葩的人，他会告诉你一些汽水要搭配起来买才卖（又不是像买一只鞋一样，为啥要这样...），也就是说买一瓶汽水则与这瓶汽水有搭配的云都要买，小黑子觉得这礼物实在是太新奇了，但是他的钱是有限的，所以他肯定是想用现有的钱买到尽量多价值的神奇汽水。

Format

Input

第一行输入三个整数，n,m,w,表示有 n瓶汽水，m个搭配和小黑子现有的钱的数目。

第二行至 n+1 行，每行有两个整数， c[i],d[i]，表示第i瓶汽水的价钱和价值。

第 n+2 至 n+1+m 行 ，每行有两个整数u[i],v[i]。表示买第 u[i]瓶汽水就必须买第 v[i]瓶汽水,同理，如果买第 v[i] 瓶就必须买第u[i]瓶。

Output

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

Samples

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

1

Limitation

1s, 1024KiB