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

见题面

见题面