//
// 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 qEnergy_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;

const ll infll = 1e18;

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

const int N=36;
const int K=26;
const int max_E_non_spanning_tree=72-((K+1)-K);

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

int n,m;
ll e[N];
ll rev_e[N];

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

int non_spanning_tree_u[max_E_non_spanning_tree];
int non_spanning_tree_v[max_E_non_spanning_tree];
int cnt_non_spanning_tree;
ll min_d_left[1ll<<(N-N/2)];
ll min_d_right[1ll<<(N/2)];
int p[N];
int local_cnt_sons[N];
ll sum_all_d;
int rem_p[N];
ll sorted_list_of_d_plus_a[N];
ll mask_on_pref_of_sorted_list_of_d_plus_a[N];

bool check_using_p(ll ANS)
{
    LOG(ANS);
    ll cur_sum_d=sum_all_d;
    for (int i=0;i<n;i++){
        local_cnt_sons[i]=0;
    }
    for (int i=1;i<n;i++){
        local_cnt_sons[p[i]]++;
    }
    ll open_mask=0;
    for (int i=0;i<n;i++){
        if (local_cnt_sons[i]==0){
            open_mask|=(1ll<<i);
        }
    }
    for (int i=0;i<n;i++){
        int id_in_sorted_list_of_d_plus_a=upper_bound(sorted_list_of_d_plus_a,sorted_list_of_d_plus_a+n,cur_sum_d+ANS)-sorted_list_of_d_plus_a;
        ll mask_good_value=0;
        if (id_in_sorted_list_of_d_plus_a!=0){
            mask_good_value=mask_on_pref_of_sorted_list_of_d_plus_a[id_in_sorted_list_of_d_plus_a-1];
        }
        ll mask_to_choose = (open_mask&mask_good_value);
        DEBUG{
            LOG(cur_sum_d);
            cerr<<"on step "<<i<<" mask_good_value was :: ";
            for (int j=0;j<n;j++){
                if (get_bit(mask_good_value,j)){
                    cerr<<j<<" ";
                }
            }
            cerr<<"\n";
            cerr<<"on step "<<i<<" mask_to_choose was :: ";
            for (int j=0;j<n;j++){
                if (get_bit(mask_to_choose,j)){
                    cerr<<j<<" ";
                }
            }
            cerr<<"\n";
        };
        if (mask_to_choose==0){
            return false;
        }
        int pos_of_min_d=min(min_d_right[mask_to_choose&((1ll<<(N/2))-1)],(n<=(N/2)?infll:min_d_left[(mask_to_choose&(((1ll<<n)-1)-((1ll<<(N/2))-1)))>>(N/2)]))&((1ll<<8)-1);
        DEBUG{
            cerr<<pos_of_min_d<<" was chosen"<<"\n";
        };
        open_mask^=(1ll<<pos_of_min_d);
        if (pos_of_min_d!=0 && (--local_cnt_sons[p[pos_of_min_d]])==0){
            open_mask|=(1ll<<p[pos_of_min_d]);
        }
        cur_sum_d-=d[pos_of_min_d];
    }
    return true;
}

ll get_ans_from_p()
{
    DEBUG{
        cerr<<"p :: ";
        for (int i=0;i<n;i++){
            cerr<<i<<","<<p[i]<<" ";
        }
        cerr<<"\n";
    };
    ll l=0,r=N*1e15;
    while (r-l>0){
        ll m=(l+r)/2;
        if (check_using_p(m)){
            r=m;
        }
        else{
            l=m+1;
        }
    }
    LOG("get_ans_from_p answer is",-l);
    return -l;
}

const int gen_test=0;
// 255214703962898
// 919016266494027

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

    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;
            d_plus_a[i]=d[i]+a[i];
        }
        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;
            d_plus_a[i]=d[i]+a[i];
        }
        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);

    DEBUG{
        for (int i=1;i<n;i++){
            LOG(i,a[i],d[i],d_plus_a[i]);
        }
    };

    for (int i=0;i<n;i++){
        sum_all_d+=d[i];
    }
    for (int i=0;i<n;i++){
        sorted_list_of_d_plus_a[i]=(d_plus_a[i]<<8)+i;
    }
    sort(sorted_list_of_d_plus_a,sorted_list_of_d_plus_a+n);
    for (int i=0;i<n;i++){
        if (i!=0){
            mask_on_pref_of_sorted_list_of_d_plus_a[i]=mask_on_pref_of_sorted_list_of_d_plus_a[i-1];
        }
        mask_on_pref_of_sorted_list_of_d_plus_a[i]|=(1ll<<(sorted_list_of_d_plus_a[i]&((1ll<<8)-1)));
        sorted_list_of_d_plus_a[i]>>=8;
    }

    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]=-infll;
        }
        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_left[(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{
        min_d_right[0]=infll;
        for (int mask=1;mask<(1ll<<(N/2));mask++){
            for (int i=0;i<(N/2);i++){
                if (get_bit(mask,i)){
                    min_d_right[mask]=min(min_d_right[mask^(1ll<<i)],(d[i]<<8)+i);
                    break;
                }
            }
        }
        min_d_left[0]=infll;
        for (int mask=0;mask<(1ll<<(N-N/2));mask++){
            for (int i=0;i<(N-N/2);i++){
                if (get_bit(mask,i)){
                    min_d_left[mask]=min(min_d_left[mask^(1ll<<i)],(d[N/2+i]<<8)+(N/2+i));
                    break;
                }
            }
        }

        assert(m-(n-1)<=max_E_non_spanning_tree);
        for (int i=1;i<n;i++){
            for (int j=0;j<n;j++){
                if (get_bit(rev_e[i],j)){
                    if ((rev_e[i]>>(j+1))==0){
                        rem_p[i]=j;
                        LOG("rem_p",i,j);
                        break;
                    }
                    else{
                        non_spanning_tree_u[cnt_non_spanning_tree]=j;
                        non_spanning_tree_v[cnt_non_spanning_tree]=i;
                        cnt_non_spanning_tree++;
                    }
                }
            }
        }
        assert(cnt_non_spanning_tree<=max_E_non_spanning_tree);
        ll ans=-infll;
        for (int mask=0;mask<(1ll<<cnt_non_spanning_tree);mask++){
            LOG("new mask of cnt_non_spanning_tree");
            for (int i=0;i<n;i++){
                p[i]=rem_p[i];
            }
            for (int i=0;i<cnt_non_spanning_tree;i++){
                if (get_bit(mask,i)){
                    LOG("changed p",non_spanning_tree_v[i],non_spanning_tree_u[i]);
                    p[non_spanning_tree_v[i]]=non_spanning_tree_u[i];
                }
            }
            ans=max(ans,get_ans_from_p());
        }
        cout<<-ans<<"\n";
    }
    return 0;
}