//
// 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(ll 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;
int rem_p[N];
int p[N];
vector<int> reb[N];

pair<ll,int> greedy_down[N];
//pair<ll,int> greedy_up[N];

void dfs_greedy_down(int start,int now,ll A,ll D)
{
    if (D>=0){
        greedy_down[start]=min(greedy_down[start],mp(A,now));
    }
    for (auto wh:reb[now]){
        dfs_greedy_down(start,wh,max(A,a[wh]-D),D+d[wh]);
    }
}

//void dfs_greedy_up(int start,int now,ll A,ll D)
//{
//    if (D>=0){
//        greedy_up[start]=min(greedy_up[start],mp(A,now));
//    }
//    if (now!=0){
//        dfs_greedy_up(start,p[now],max(A,d[p[now]]+a[p[now]]-D),D-d[p[now]]);
//    }
//}

void dfs_greedy(int now)
{
    greedy_down[now]=mp(infll,-1);
    dfs_greedy_down(now,now,a[now],d[now]);
//    greedy_up[now]=mp(infll,-1);
//    dfs_greedy_up(now,now,d[now]+a[now],-d[now]);
    for (auto wh:reb[now]){
        dfs_greedy(wh);
    }
}

bool in_q[N];
int cur_cnt_down[N];
bool mark[N];

bool check_using_p(ll ANS)
{
    for (int i=0;i<n;i++){
        mark[i]=0;
    }
    {
        for (int i=0;i<n;i++){
            in_q[i]=0;
        }
        in_q[0]=1;
        ll D=0;
        while (1){
            bool ok=0;
            for (int i=0;i<n;i++){
                if (in_q[i]){
                    if (D-greedy_down[i].fir>=-ANS){
                        int cur=greedy_down[i].sec;
                        int nxt_cur=-1;
                        while (1){
                            mark[cur]=1;
                            D+=d[cur];
                            for (auto wh:reb[cur]){
                                if (wh!=nxt_cur){
                                    in_q[wh]=1;
                                }
                            }
                            if (cur==i){
                                break;
                            }
                            nxt_cur=cur;
                            cur=p[cur];
                        }
                        in_q[i]=0;
                        ok=1;
                        break;
                    }
                }
            }
            if (!ok){
                break;
            }
        }
    }

    {
        for (int i=0;i<n;i++){
            cur_cnt_down[i]=0;
        }
        for (int i=1;i<n;i++){
            cur_cnt_down[p[i]]++;
        }
        ll D=0;
        for (int i=0;i<n;i++){
            D+=d[i];
        }
        while (1){
            bool ok=0;
            for (int i=0;i<n;i++){
                if (cur_cnt_down[i]==0){
                    ll cur_D=-d[i];
                    ll cur_A=d[i]+a[i];
                    int cur=i;
                    while (cur_cnt_down[cur]<=1){
                        if (cur_D>=0 && D-cur_A>=-ANS){
                             int ff=i;
                             while (1){
                                 cur_cnt_down[ff]--;
                                 D-=d[ff];
                                 mark[ff]=1;
                                 if (ff==cur){
                                     if (ff!=0){
                                         cur_cnt_down[p[ff]]--;
                                     }
                                     break;
                                 }
                                 ff=p[ff];
                             }
                        }
                        if (cur==0){
                            break;
                        }
                        cur=p[cur];
                        cur_A=max(cur_A,d[cur]+a[cur]-cur_D);
                        cur_D-=d[cur];
                    }
                }
            }
            if (!ok){
                break;
            }
        }
    }

    for (int i=0;i<n;i++){
        if (!mark[i]){
            return false;
        }
    }
    return true;
}

ll get_ans_from_p(ll known_ans)
{
    DEBUG{
        cerr<<"p :: ";
        for (int i=0;i<n;i++){
            cerr<<i<<","<<p[i]<<" ";
        }
        cerr<<"\n";
    };

    for (int i=0;i<n;i++){
        reb[i].clear();
    }
    for (int i=1;i<n;i++){
        reb[p[i]].pb(i);
    }
    dfs_greedy(0);

    ll l=0,r=min(ll(N*1e15+10),(-known_ans));
    if (!check_using_p(r)){
        return known_ans;
    }
    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;
}

// 255214703962898
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);

    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 (1 && 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(ans));
        }
        cout<<-ans<<"\n";
    }
    return 0;
}