Minimum Trading Cost

You are given N types of goods numbered from 0 to N-1, where the i-th good is valued at \(v_i\) units of money.

There are M merchants numbered from 0 to M-1. At the j-th merchant, you can exchange your good \(x_j\) for the merchant’s good \(y_j\). The transaction is carried out based on the values of the goods. In particular, if \(v_{x_j} > v_{y_j}\), then the merchant pays you \(v_{x_j} - v_{y_j}\) units of money; otherwise, you must pay him \(v_{y_j} - v_{x_j}\) units. In addition, each transaction costs an extra fee of \(1\) unit regardless of the goods exchanged.

You start with good a and wish to eventually obtain good b through a sequence of such trades. Compute the minimum total cost required to do so. Note that the minimum cost may be negative, which means that you can actually earn money in the process. It is guaranteed that there exists at least one sequence of trades to go from a to b.

Explanation: Each available trade from good \(x\) to good \(y\) has a cost defined by \[ \text{cost} = 1 + v_y - v_x, \] which can be negative if \(v_x > v_y\) (since you effectively earn money, aside from paying the fee). Use an appropriate algorithm (e.g. Bellman–Ford) to compute the minimum cost path in this directed graph.

inputFormat

The input consists of:

• The first line contains four integers \(N\), \(M\), \(a\), and \(b\) separated by spaces.
• The second line contains \(N\) integers, where the \(i\)-th integer is \(v_i\), the value of the i-th good.
• Each of the next \(M\) lines contains two integers \(x_j\) and \(y_j\), indicating that you can exchange good \(x_j\) for good \(y_j\) at the j-th merchant.

It is guaranteed that there is at least one sequence of trades from good \(a\) to good \(b\).

outputFormat

Output a single integer – the minimum total cost needed to obtain good \(b\) starting from good \(a\). This cost may be negative if you end up earning money.

sample

3 3 0 2
5 3 6
0 1
1 2
0 2

2