Rapid Mastery

In a dream you foresaw that one fatal problem in the CPCI contest would be the one to bring you down. Determined to avoid the tragedy in reality, you decided to quickly master the skills necessary to solve the problem.

The problem involves a knowledge roadmap which can be represented as a directed acyclic graph (DAG) with n knowledge points and m dependency relations. Each knowledge point is numbered from 1 to n. For each knowledge point i, you have two options:

• You can learn it by following the prerequisites. That is, after mastering all its prerequisite knowledge points, you can learn i in a_i time.
• Alternatively, you can bypass the prerequisites by spending a longer time of b_i.

You are to determine the minimum total time required to master a target knowledge point X. Note that once a knowledge point is learned (by either method) it does not need to be relearned if required as a prerequisite for multiple other points.

You may assume that the dependency graph is a DAG and, for the purpose of this problem, the prerequisites for any node will not be shared among multiple branches in a way that affects the optimal cost (i.e. you may use the local recurrence below):

$$\text{dp}(i)=\min\Big( b_i,\, a_i+\sum_{p\in P(i)}\text{dp}(p)\Big), $$

where P(i) is the set of immediate prerequisites of knowledge point i (if there are no prerequisites, the sum is considered 0). The answer to the problem is dp(X).

inputFormat

The input is given from standard input and consists of the following:

1. A line containing three integers: n m X, where n is the number of knowledge points, m is the number of dependency relations, and X is the target knowledge point you need to master.
2. A line of n integers: a1 a2 ... an, where ai denotes the time to learn knowledge point i by following its prerequisites.
3. A line of n integers: b1 b2 ... bn, where bi is the time to directly conquer knowledge point i (skipping prerequisites).
4. m lines each containing two integers u v, indicating that knowledge point u is a prerequisite for knowledge point v.

You may assume that the graph is a DAG.

outputFormat

Output a single integer, the minimum total time required to master knowledge point X.

sample

3 2 3
3 2 1
5 4 3
1 3
2 3

3