//
// Created by Barichek on 21.07.2023 09:32:09
//

#include <bits/stdc++.h>

#define F first
#define S second
#define MP make_pair
#define PB push_back

#define all(a) a.begin(), a.end()
#define len(a) (int) (a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

#ifdef Energy_is_not_over
#define DEBUG for (bool ____DEBUG = true; ____DEBUG; ____DEBUG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = -1, inf = 1000111222;

inline bool get_bit(int mask,int bit)
{
    return (mask>>bit)&1;
}

const int N=36;
const int K=26;

ll sum_d_left[1ll<<(N-N/2)];
ll sum_d_right[1ll<<(N/2)];
ll dp[1ll<<K];

ll a[N];
ll d[N];

int e[N];
int rev_e[N];

const int gen_test=0;

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,m;
    if (gen_test==1){
        const ll M=1e15;
        mt19937_64 gen64(474747);
        n=K;
        m=72-K;
        for (int i=1;i<n;i++){
            ll aa,bb;
            aa=gen64()%M+1;
            bb=gen64()%M+1;
            a[i]=aa;
            d[i]=bb-aa;
        }
        for (int i=0;i<m;i++){
            int u,v;
            if (i<n-1){
                u=i;
                v=i+1;
            }
            else{
                do{
                    u=gen64()%n;
                    v=gen64()%n;
                }
                while (u>=v);
            }
            e[u]|=(1ll<<v);
            rev_e[v]|=(1ll<<u);
        }
    }
    else{
        cin>>n>>m;
        for (int i=1;i<n;i++){
            ll aa,bb;
            cin>>aa>>bb;
            a[i]=aa;
            d[i]=bb-aa;
        }
        for (int i=0;i<m;i++){
            int u,v;
            cin>>u>>v;
            u--;
            v--;
            e[u]|=(1ll<<v);
            rev_e[v]|=(1ll<<u);
        }
    }
    assert(n<=N);
    if (n<=K){
        for (int mask=0;mask<(1ll<<(N/2));mask++){
            for (int i=0;i<(N/2);i++){
                if (get_bit(mask,i)){
                    sum_d_right[mask]=sum_d_right[mask^(1ll<<i)]+d[i];
                    break;
                }
            }
        }
        for (int mask=0;mask<(1ll<<(N-N/2));mask++){
            for (int i=0;i<(N-N/2);i++){
                if (get_bit(mask,i)){
                    sum_d_left[mask]=sum_d_left[mask^(1ll<<i)]+d[N/2+i];
                    break;
                }
            }
        }
        for (int mask=0;mask<(1ll<<n);mask++){
            dp[mask]=-1e18;
        }
        dp[(1ll<<0)]=0;
        for (int mask=0;mask<(1ll<<n);mask++){
            ll cur_sum_d = sum_d_right[mask&((1ll<<(N/2))-1)] + (n<=(N/2)?0:sum_d_right[(mask&(((1ll<<n)-1)-((1ll<<(N/2))-1)))>>(N/2)]);
            for (int i=0;i<n;i++){
                if (!get_bit(mask,i) && (rev_e[i]&mask)!=0){
                    LOG("upd",bitset<10>(mask),i,dp[mask],cur_sum_d-a[i]);
                    dp[mask^(1ll<<i)]=max(dp[mask^(1ll<<i)],min(dp[mask],cur_sum_d-a[i]));
                }
            }
        }
        cout<<-dp[(1ll<<n)-1]<<"\n";
    }
    else{
        assert(0);
    }
    return 0;
}