#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

const ll inf=1e18;
struct SegTree
{
    struct Node
    {
        ll lzs=0;
        pll Min={0, 0}, lzm={inf, 0};
        Node(ll type=0) {if (type) Min.fi=inf;}

        Node operator + (const Node &o) const
        {
            Node ans; 
            ans.Min=min(Min, o.Min);
            return ans;
        }

        void act(ll ad, pll mi)
        {
            Min.fi+=ad, Min=min(Min, mi);
            lzs+=ad, lzm.fi+=ad, lzm=min(lzm, mi);
        }
    };

    ll n;
    vector <Node> St;
    SegTree (ll n): n(n) {St.resize(n*4+1);}
    
    void Move(ll i)
    {
        St[i*2].act(St[i].lzs, St[i].lzm);
        St[i*2+1].act(St[i].lzs, St[i].lzm);
        St[i].lzs=0, St[i].lzm={inf, 0};
    }

    void update(ll i, ll Start, ll End, ll l, ll r, ll ad, pll mi)
    {
        if (Start>r || End<l) return;
        if (Start>=l && End<=r) {St[i].act(ad, mi); return;}
        ll mid=(Start+End)/2; Move(i);
        if (l<=mid) update(i*2, Start, mid, l, r, ad, mi);
        if (r>=mid+1) update(i*2+1, mid+1, End, l, r, ad, mi);
        St[i]=St[i*2]+St[i*2+1];
    }
    void update(ll l, ll r, ll ad, pll mi) {update(1, 1, n, l, r, ad, mi);}

    Node query(ll i, ll Start, ll End, ll l, ll r)
    {
        if (Start>r || End<l) return Node(1);
        if (Start>=l && End<=r) return St[i];
        ll mid=(Start+End)/2; Move(i);
        if (l>mid) return query(i*2+1, mid+1, End, l, r);
        if (r<mid+1) return query(i*2, Start, mid, l, r);
        return query(i*2, Start, mid, l, r)+query(i*2+1, mid+1, End, l, r);
    }
    Node query(ll l, ll r) {return query(1, 1, n, l, r);}
};

ll n, m, l[10005], r[10005];
void init(int N, int M, vector <int> L, vector <int> R)
{
    n=N, m=M;
    for (ll i=0; i<n; i++)
        l[i]=L[i], r[i]=R[i];
    //compress numbers
    {
        vector <ll> num;
        for (ll i=0; i<n; i++)
            num.pb(l[i]), num.pb(r[i]);
        sort(num.begin(), num.end());
        num.resize(unique(num.begin(), num.end())-num.begin());
        for (ll i=0; i<n; i++)
        {
            l[i]=lower_bound(num.begin(), num.end(), l[i])-num.begin()+1;
            r[i]=lower_bound(num.begin(), num.end(), r[i])-num.begin()+1;
        }
        m=num.size();
    }
    auto Try=[&](ll A, ll B)
    {
        SegTree S(m);
        for (ll i=0; i<n; i++)
        {
            S.update(l[i], r[i], B, {inf, 0});
            SegTree::Node best=S.query(1, m); 
            best.Min.se++, S.update(1, m, 0, best.Min);
        }
        ll cost, a, b;
        tie(cost, a)=S.query(1, m).Min, b=(cost-a*A)/B;
        return mp(a, b);
    };
}

ll minimize(int A, int B)
{
    SegTree S(m);
    for (ll i=0; i<n; i++)
    {
        S.update(l[i], r[i], B, {inf, 0});
        SegTree::Node best=S.query(1, m); 
        S.update(1, m, 0, {best.Min.fi+A, best.Min.se+1});

    }
    return S.query(1, m).Min.fi;
}

// int main()
// {
//     ios_base::sync_with_stdio(0);
//     cin.tie(0); cout.tie(0);
//     freopen("input.txt", "r", stdin);
//     freopen("output.txt", "w", stdout);
//     ll n, m, q; cin >> n >> m >> q;
//     int l[n], r[n];
//     for (ll i=0; i<n; i++)
//         cin >> l[i] >> r[i];
//     init(n, m, l, r);
//     for (ll i=0; i<q; i++)
//     {
//         ll A, B; cin >> A >> B;
//         cout << minimize(A, B) << "\n";
//     }
// }