Language: C++

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
typedef long long ll;
int limit[N] , bonus[N] , need[N];

int n , m;
vector<int> adj[N];

struct CmpLimit { 
    bool operator() (int x , int y) {return limit[x] < limit[y];}
};

int par[N] , *unlocked = par , init = 0;
ll money[N];
set<int , CmpLimit> out[N];

struct Info {
    int x , cost;
    Info() {}
    Info(int x , int cost) : x(x) , cost(cost) {}
    bool operator< (const Info &t) const {return cost < t.cost;}
};
set<Info> point;
void modifycost(int pos , int val) {
    if(unlocked[pos] || need[pos] <= val)
        return;
    point.erase(Info(pos , need[pos]));
    point.insert(Info(pos , need[pos] = val));
}
int find(int x) {return x == par[x] ? x : par[x] = find(par[x]);}

void unlock(int x) ;
void merge(int x , int y) ;

void unlock(int x) {
    par[x] = x;
    money[x] = bonus[x];
    for(auto y : adj[x]) {
        int p = find(x);
        if(find(y) == p) continue;

        if(unlocked[y]) merge(x , y);
        else {
            if(money[p] + init >= limit[y]) unlock(y);
            else {
                out[p].insert(y);
                modifycost(y , (int)max(limit[y] - money[p] , 0LL));                
            }
        }
    }
}


void merge(int x , int y) {
    x = find(x) , y = find(y);
    if(x == y) return ;

    if(out[x].size() > out[y].size()) swap(x , y);
    for(auto t : out[x]) if(find(t) != y) out[y].insert(t);
    out[x].clear();
    par[x] = y , money[y] += money[x];

    while(out[y].size()) {
        x = *out[y].begin();
        if(find(x) == y) {
            out[y].erase(*out[y].begin());
            continue;
        }
        if(money[y] + init >= limit[x]) {
            out[y].erase(*out[y].begin());
            unlock(x);
            y = find(y);
            continue;
        }
        modifycost(x , (int)max(limit[x] - money[y] , 0LL));
        break;
    }
}

int main() {
    scanf("%d %d" , &n , &m);
    for(int i = 1 ; i <= n ; ++i) {
        scanf("%d %d" , limit + i , bonus + i);
        limit[i] -= bonus[i] , need[i] = max(0 , limit[i]);
        point.insert(Info(i , need[i]));
    }
    for(int i = 1 , x , y; i <= m ; ++i) {
        scanf("%d %d" , &x , &y);
        adj[x].push_back(y) , adj[y].push_back(x);
    }
    while(point.size()) {
        int x = point.begin()->x , c = point.begin()->cost;
        point.erase(point.begin());
        if(unlocked[x]) continue;
        init = max(init , c);
        unlock(x);
    }
    ll ans = init;
    for(int i = 1 ; i <= n ; ++i) ans += bonus[i];
    cout << ans << endl;
    return 0;
}
/*
9 10
131 2
98 79
242 32
231 38
382 82
224 22
140 88
209 70
164 64
6 8
1 6
1 4
1 3
4 7
4 9
3 7
3 9
5 9
2 5

582
*/

Compiler output:
In file included from /usr/include/c++/14/map:62,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:152,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_tree.h: In instantiation of 'static const _Key& std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_S_key(_Const_Link_type) [with _Key = int; _Val = int; _KeyOfValue = std::_Identity<int>; _Compare = CmpLimit; _Alloc = std::allocator<int>; _Const_Link_type = const std::_Rb_tree_node<int>*]':
/usr/include/c++/14/bits/stl_tree.h:2116:47:   required from 'std::pair<std::_Rb_tree_node_base*, std::_Rb_tree_node_base*> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_get_insert_unique_pos(const key_type&) [with _Key = int; _Val = int; _KeyOfValue = std::_Identity<int>; _Compare = CmpLimit; _Alloc = std::allocator<int>; key_type = int]'
 2116 |           __comp = _M_impl._M_key_compare(__k, _S_key(__x));
      |                                                ~~~~~~^~~~~
/usr/include/c++/14/bits/stl_tree.h:2169:4:   required from 'std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique(_Arg&&) [with _Arg = const int&; _Key = int; _Val = int; _KeyOfValue = std::_Identity<int>; _Compare = CmpLimit; _Alloc = std::allocator<int>]'
 2169 |         = _M_get_insert_unique_pos(_KeyOfValue()(__v));
      |           ^~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_set.h:514:25:   required from 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = int; _Compare = CmpLimit; _Alloc = std::allocator<int>; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<int, int, std::_Identity<int>, CmpLimit, std::allocator<int> >::const_iterator; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other = std::allocator<int>; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key> = __gnu_cxx::__alloc_traits<std::allocator<int>, int>::rebind<int>; typename _Alloc::value_type = int; value_type = int]'
  514 |           _M_t._M_insert_unique(__x);
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~
a.cc:48:30:   required from here
   48 |                 out[p].insert(y);
      |                 ~~~~~~~~~~~~~^~~
/usr/include/c++/14/bits/stl_tree.h:768:15: error: static assertion failed: comparison object must be invocable as const
  768 |               is_invocable_v<const _Compare&, const _Key&, const _Key&>,
      |               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_tree.h:768:15: note: 'std::is_invocable_v<const CmpLimit&, const int&, const int&>' evaluates to false