Maximizing Potion Profit

A shop sells N types of potions. Each potion type i has a purchase price \(c_i\) and a resale (recycling) value \(r_i\). Xiao S has \(V\) yuan of initial money which he can use to buy potions. Moreover, he knows M magic transformations (spells). Each spell transforms a potion of one type into another type. Formally, each spell is described by two integers \(a\) and \(b\) (1-indexed), meaning that a potion of type \(a\) can be transformed into a potion of type \(b\) in one use of magic. He is allowed to use magic at most \(K\) times in one day in total (the spells may be applied in sequence on the same potion). Note that the money earned by selling potions cannot be reinvested (i.e. you may only use your initial capital \(V\) to purchase potions).

When a potion is sold, you receive its current resale value. Initially, if you buy a potion of type \(i\), its resale value is \(r_i\). However, you may choose to transform it using a sequence of spells. If you start with a potion of type \(i\) and apply a sequence of spells (using a total of \(j\) operations, where \(0 \le j \le K\)) you may be able to obtain a potion of some type with a higher resale value. The transformation is defined as follows:

• Define \(dp[i][0] = r_i\).
• For \(j \ge 1\), \(dp[i][j] = \max\Big( dp[i][j-1], \; \max_{\text{spell } (i\to b)}\; dp[b][j-1]\Big)\). That is, with at most \(j\) spells starting from type \(i\), the maximum resale value achievable is \(dp[i][j]\) (here you are allowed to choose not to use a spell).

For each purchase option you decide on an initial potion type \(i\) and you plan to use exactly \(j\) spells on it (\(0 \le j \le K\)). The net profit from that potion is then \(dp[i][j] - c_i\). You may buy as many potions (using the same option repeatedly) as you want as long as the total initial purchase cost does not exceed \(V\) and the total number of spells used does not exceed \(K\). Your goal is to maximize the total profit (i.e. the sum over all chosen potions of \(dp[i][j] - c_i\)) under these constraints.

Input constraints:

• The first line contains four integers: \(N\), \(M\), \(K\), and \(V\) (the number of potion types, the number of spells, the maximum allowed spell uses in a day, and the initial money).
• The next \(N\) lines each contain two positive integers \(c_i\) and \(r_i\) — the purchase cost and the resale value of the \(i\)th potion.
• The next \(M\) lines each contain two integers \(a\) and \(b\) indicating that there is a spell which can transform a potion of type \(a\) to type \(b\).

Output: Output a single integer representing the maximum profit Xiao S can make in one day.

inputFormat

The input begins with a line containing four space‐separated integers \(N\), \(M\), \(K\), and \(V\). The following \(N\) lines each contain two integers \(c_i\) and \(r_i\) describing the cost and resale value of the \(i\)th potion. Then \(M\) lines follow; each contains two integers \(a\) and \(b\) (1-indexed) indicating that a potion of type \(a\) can be transformed into a potion of type \(b\) using one spell.

outputFormat

Print a single integer denoting the maximum attainable profit.

sample

3 2 2 10
3 5
4 6
5 10
1 3
2 3

14