1859: 【基础】采购礼品

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:1 Solved:1

Description

王老师来到商店为同学们采购礼品。这家店有n种礼品(编号是1~n),每种礼品只有1件。老板为了促销,对礼品进行搭配销售,有关联性的礼品必须都要采购(奇怪的规定),比如1号礼品和3号礼品搭配了,3号和8号礼品搭配了,那么王老师想要买1号礼品的话,就需要把3号和8号礼品都买了。现给定每种礼品的价钱和价值,请问在有限的钱w的情况下,能够买到礼品的最大价值是多少?

Input

第一行输入三个整数,n,m,w,表示有n种礼品,m个搭配和你现有的钱的数目。

第二行至n+1行,每行有两个整数,c、d,表示第i种礼品的价钱和价值。(1≤c,d≤105

第n+2至n+1+m行 ,每行有两个整数,u、v,表示u号礼品和v号礼品是有关联的,已经形成搭配销售的关系。

1≤n,w≤104,0≤m≤5×103

Output

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

Sample Input Copy

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

Sample Output Copy

1