Problem Description

There are $N$ types of commodities in the market, numbered from $0$ to $N-1$. The $i$-th commodity is worth $v_i$ yuan.

There are $M$ merchants, numbered from $0$ to $M-1$. With the $j$-th merchant, you can exchange your $x_j$-th commodity for the $y_j$-th commodity in the merchant's possession. Each merchant trades according to the value of the commodities. Specifically, if $v_{x_j} > v_{y_j}$, the merchant will pay you $v_{x_j} - v_{y_j}$ yuan; otherwise, you need to pay the merchant $v_{x_j} - v_{y_j}$ yuan. In addition, the merchant charges a fee of 1 yuan for each transaction, regardless of the value of the commodities being traded.

You currently possess commodity $a$ and wish to obtain commodity $b$ through some exchanges. What is the minimum amount of money you need to spend? (Of course, this minimum cost could also be negative, indicating that you can make some profit while achieving your goal.)

Input Format

The first line contains four integers $N$, $M$, $a$, and $b$, representing the number of commodities, the number of merchants, the commodity you hold, and the commodity you wish to obtain, respectively. It is guaranteed that $0 \le a, b < N$ and $a \ne b$.

The second line contains $N$ positive integers separated by single spaces, $v_0, v_1, \ldots, v_{N-1}$, representing the value of each commodity in order. It is guaranteed that $1 \le v_i \le 10^9$.

The next $M$ lines each contain two integers $x_j$ and $y_j$, indicating that with the $j$-th merchant, you can exchange the $x_j$-th commodity for the $y_j$-th commodity. It is guaranteed that $0 \le x_j, y_j < N$ and $x_j \ne y_j$.

Output Format

Output a single integer on one line, representing the minimum cost. Specifically, if it is impossible to obtain commodity $b$ through exchanges, output No solution.

Sample Input and Output

Input Sample #1

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

Output Sample #1

5

Input Sample #2

3 3 0 2
100 2 4
0 1
1 2
0 2

Output Sample #2

-95

Input Sample #3

4 4 3 0
1 2 3 4
1 0
0 1
3 2
2 3

Output Sample #3

No solution

Notes

Data Range

For 30% of the test cases, it is guaranteed that $N \le 10$ and $M \le 20$.

For 70% of the test cases, it is guaranteed that $N \le 10^3$ and $M \le 10^4$.

For 100% of the test cases, it is guaranteed that $N \le 10^5$ and $M \le 2 \times 10^5$.

见题面 Input 部分

见题面 Output 部分