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
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define int long long
using namespace std;
typedef pair<int,int>P;

int s,t,n,m,a[100009],d[100009];
priority_queue<P,vector<P>,greater<P> >q;
vector<P>v[100009];

signed main(){
  r(i,100009)d[i]=1e15;
  cin>>n>>m>>s>>t; s--; t--;
  r(i,n)cin>>a[i];
  r(i,n-1)v[i+1].push_back(P(i,0));
  r(i,m){
    int q,w;
    cin>>q>>w; q--; w--;
    v[q].push_back(P(w,a[w]));
  }
  q.push(P(0,s));
  while(!q.empty()){
    P p=q.top();q.pop();
    int now=p.second;
    int cost=p.first;
    if(d[now]<cost)continue;
    r(i,v[now].size()){
      int nex=v[now][i].first;
      int ncos=cost+v[now][i].second;
      if(d[nex]<=ncos)continue;
      d[nex]=ncos;
      q.push(P(ncos,nex));
    }
  }
  cout<<d[t]<<endl;
}
