#include<bits/stdc++.h>
using namespace std;
// #include<atcoder/all>
// using namespace atcoder;
// using mint=atcoder::modint998244353;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define int long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rng(i,l,r) for(int i=(l);i<(r);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrng(i,l,r) for(int i=(r)-1;i>=(l);i--)
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
struct fast_io{fast_io(){std::cin.tie(nullptr)->sync_with_stdio(false);}}_;
namespace cplib {
template <class T>
struct slope_trick {
const T INF = std::numeric_limits<T>::max() / 3;
T min_f;
std::priority_queue<T, std::vector<T>, std::less<>> L;
std::priority_queue<T, std::vector<T>, std::greater<>> R;
T add_l, add_r;
void push_R(const T& a) { R.push(a - add_r); }
T top_R() const {
if (R.empty())
return INF;
else
return R.top() + add_r;
}
T pop_R() {
T val = top_R();
if (!R.empty()) R.pop();
return val;
}
void push_L(const T& a) { L.push(a - add_l); }
T top_L() const {
if (L.empty())
return -INF;
else
return L.top() + add_l;
}
T pop_L() {
T val = top_L();
if (!L.empty()) L.pop();
return val;
}
size_t size() { return L.size() + R.size(); }
slope_trick() : min_f(0), add_l(0), add_r(0) {}
struct Query {
T lx, rx, min_f;
};
// return min f(x)
Query query() const { return (Query){top_L(), top_R(), min_f}; }
// f(x)+=a
void add_all(const T& a) { min_f += a; }
// add \_
// f(x) += max(a - x, 0)
void add_a_minus_x(const T& a) {
min_f += std::max(T(0), a - top_R());
push_R(a);
push_L(pop_R());
}
// add _/
// f(x) += max(x - a, 0)
void add_x_minus_a(const T& a) {
min_f += std::max(T(0), top_L() - a);
push_L(a);
push_R(pop_L());
}
// add \/
// f(x) += abs(x - a)
void add_abs(const T& a) {
add_a_minus_x(a);
add_x_minus_a(a);
}
// \/ -> \_
// f_{new} (x) = min f(y) (y <= x)
void clear_right() {
while (!R.empty()) R.pop();
}
// \/ -> _/
// f_{new} (x) = min f(y) (y >= x)
void clear_left() {
while (!L.empty()) L.pop();
}
// \/ -> \_/
// f_{new} (x) = min f(y) (x-b <= y <= x-a)
void shift(const T& a, const T& b) {
assert(a <= b);
add_l += a;
add_r += b;
}
// \/. -> .\/
// f_{new} (x) = f(x - a)
void shift(const T& a) { shift(a, a); }
// destroy L,R
T get(const T& x) {
T ret = min_f;
while (!L.empty()) {
ret += std::max(T(0), pop_L() - x);
}
while (!R.empty()) {
ret += std::max(T(0), x - pop_R());
}
return ret;
}
void merge(slope_trick& st) {
if (st.size() > size()) {
swap(st.L, L);
swap(st.R, R);
swap(st.add_l, add_l);
swap(st.add_r, add_r);
}
while (!st.R.empty()) {
add_x_minus_a(st.pop_R());
}
while (!st.L.empty()) {
add_a_minus_x(st.pop_L());
}
min_f += st.min_f;
}
};
/*
Slope Trick
ref :
- https://ei1333.github.io/library/structure/others/slope-trick.hpp.html
- https://maspypy.com/slope-trick-1-%E8%A7%A3%E8%AA%AC%E7%B7%A8
*/
} // namespace cplib
signed main(){
int N,M;cin>>N>>M;
vector<vector<pair<int,int>>> g(N+M);
rng(i,1,N+M){
int p,c;cin>>p>>c;p--;
g[p].push_back({i,c});
}
vector<cplib::slope_trick<int>> vst(N+M);
rrep(i,N+M){
if(N<=i){
vst[i].add_abs(0);
}
for(auto&&[e,c]:g[i]){
while(vst[e].R.size()>1){
vst[e].pop_R();
}
int l=vst[e].pop_L(),r=vst[e].pop_R();
vst[e].push_L(l+c),vst[e].push_R(r+c);
vst[i].merge(vst[e]);
}
}
cout<<vst[0].query().min_f<<"\n";
}
