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

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);
    }
}

struct elem
{
    ll a,b;
};

elem merge(elem lhs,elem rhs)
{
    ll a=max(lhs.a,lhs.a-lhs.b+rhs.a);
    return elem{a,lhs.b+rhs.b-lhs.a-rhs.a+a};
}

bool operator<(const elem& lhs,const elem& rhs)
{
    bool negl = lhs.a > lhs.b;
    bool negr = rhs.a > rhs.b;
    if (negl != negr) return negl < negr;
    else if (negl == 0) return lhs.a < rhs.a;
    else return lhs.b > rhs.b;
}

elem elems[N];

set<pair<elem,int>> setik;

int ppp[N];
int f_ppp(int v)
{
    return ppp[v]==v?v:ppp[v]=f_ppp(ppp[v]);
}

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

    ppp[0]=0;
    elems[0]=elem{0,0};
    setik.clear();
    for (int i=1;i<n;i++){
        ppp[i]=i;
        elems[i]=elem{a[i],d[i]+a[i]};
        setik.insert(mp(elems[i],i));
    }
    while (!setik.empty()){
        DEBUG{
            cerr<<"setik :: ";
            for (auto i:setik){
                cerr<<i.fir.a<<","<<i.fir.b<<" ";
            }
            cerr<<"\n";
        }
        auto now=*setik.begin();
        LOG(now.sec);
        setik.erase(setik.begin());
        ppp[now.sec]=p[now.sec];
        int u=f_ppp(now.sec);
        if (u==0){
            elems[0]=merge(elems[0],now.fir);
            LOG("to elems[0]",now.fir.a,now.fir.b);
        }
        else{
            LOG("to elems[u]",u,now.fir.a,now.fir.b);
            setik.erase(mp(elems[u],u));
            elems[u]=merge(elems[u],now.fir);
            setik.insert(mp(elems[u],u));
        }
    }
    return elems[0].a;

//    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;
const bool repeat=1;
const bool not_goto_start=1;

mt19937_64 gen64(123);

/*
5 5
2 1
1 1
2 1
2 2
1 2
2 3
3 4
4 5
1 4
*/

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

    LOG(elem{2,-1}<elem{2,0});
    LOG(elem{2,0}<elem{2,-1});

    start_of_program:;

    for (int i=0;i<N;i++){
        e[i]=0;
        rev_e[i]=0;
    }

    if (gen_test==1){
        static int test_id=0;
        const ll M=2;
        n=5;
        m=5;
        cout<<"test_id :: "<<(test_id++)<<"\n";
        cout<<"new test"<<"\n";
        cout<<n<<" "<<m<<"\n";
        for (int i=1;i<n;i++){
            ll aa,bb;
            aa=gen64()%M+1;
            bb=gen64()%M+1;
            cout<<aa<<" "<<bb<<"\n";
            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);
            }
            cout<<u+1<<" "<<v+1<<"\n";
            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;
//    }

    ll ans_for_repeat=-1;
    if (repeat || 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";
        ans_for_repeat=-dp[(1ll<<n)-1];
    }
    if (repeat || n>K){
//        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);
        cnt_non_spanning_tree=0;
        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=min(ans,get_ans_from_p(ans));
        }
        cout<<ans<<"\n";
        if (repeat && ans!=ans_for_repeat){
            cerr<<ans<<" "<<ans_for_repeat<<"\n";
            exit(123);
        }
    }
    if (repeat && !not_goto_start){
        goto start_of_program;
    }
    return 0;
}