Dimension travel

problem

Dimension exists from $1$ dimension to $N$ dimension. AOR Ika can move between dimensions. Specifically, when AOR Ika is in the $i$ dimension, she can move freely to the $j$ dimension ($i> j$), but in the $k$ dimension ($i <k$). You need to use magic to move to.

AOR Ika can use $M$ types of magic and is numbered $1, 2, \ dots, M$. The $i$ th magic allows you to move from the $a_i$ dimension to the $b_i$ dimension. This can only be used when you are in the $a_i$ dimension.

When you go to the $i$ dimension, you will receive a dimension-specific "curse of dimensionality". AOR Ika takes $d_i$ damage due to the "curse of dimensionality" of the $i$ dimension. If you receive the "curse of dimensionality" of the $i$ dimension, you will not receive the "curse of dimensionality" of the $j$ dimension ($i> j$) forever.

Find the minimum total damage inflicted when AOR Ika moves from the $s$ dimension to the $t$ dimension. However, AOR Ika-chan has already received the "curse of dimensionality" of the $s$ dimension, and we will not consider the damage. Also, AOR Ika is guaranteed to be able to go to the $t$ dimension.

output

Output the minimum value of the total damage received by AOR Ika-chan. Also, output a line break at the end.

Example

Input

3 1 2 3 1 2 3 1 3

Output

3

inputFormat

outputFormat

output

Output the minimum value of the total damage received by AOR Ika-chan. Also, output a line break at the end.

Example

Input

3 1 2 3 1 2 3 1 3

Output

3

样例

3 1 2 3
1 2 3
1 3

3