Background

Special for beginners, ^_^

Description

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

但是 Joe 的钱有限，所以他希望买的价值越多越好。

Format

Input

第 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$。

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 for each test case.

$30\%$ 的数据保证：$n≤100$

$50\%$ 的数据保证：$n≤1,000；m≤100；w≤1,000$

$100\%$ 的数据保证：$n≤10,000；0≤m≤5000；w≤10,000$