#include "breakthru.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
#define MP make_pair

namespace{
    const ll MAXN=1e4;

    ll n,m;
    pll a[MAXN+100];
    ll eval(pll times,ll costX,ll costY){
        return times.fi*costX+times.se*costY;
    }
    namespace seg{
        const ll SZ = (MAXN*2+1)*4;
        ll A,B;
        pll tree[SZ+100];
        pair <pll,ll> lazy[SZ+100];
        pair <pll,ll> default_lazy;
        vector <ll> val;
        void init_value(){
            val.push_back(0);
            for (ll i=0;i<n;i++){
                if (a[i].fi>0)val.push_back(a[i].fi-1);
                if (a[i].se+1<m)val.push_back(a[i].se+1);
            }
            sort(val.begin(),val.end());
            val.resize(unique(val.begin(),val.end())-val.begin());
        }
        void build(ll id,ll l,ll r){
            tree[id] = MP(0,0);
            lazy[id] = default_lazy;
            if (l != r){
                ll mid = (l + r) >> 1;
                build(id<<1,l,mid);
                build(id<<1|1,mid+1,r);
            }
        }
        void reset(ll AA,ll BB){
            A=AA,B=BB;
            default_lazy = MP(MP(n+1,n+1),0);
            build(1,0,sz(val)-1);
        }
        pll better(pll x,pll y){
            if (eval(x,A,B) < eval(y,A,B))return x;
            else return y;
        }
        void push_minimize(ll id,pll min1){
            lazy[id].fi = better(lazy[id].fi,min1);
            tree[id] = better(tree[id],min1);
        }
        void push_add(ll id,ll val){
            lazy[id].se += val;
            lazy[id].fi.se+=val;
            tree[id].se += val;
        }
        void push_all(ll id,pair <pll,ll> val){
            push_add(id,val.se);
            push_minimize(id,val.fi);
        }
        void lz(ll id){

            if (lazy[id] != default_lazy){
//                cout<<"PUSHDOWN "<<id<<endl;
                push_all(id<<1,lazy[id]);
                push_all(id<<1|1,lazy[id]);
                lazy[id] = default_lazy;
//                cout<<"PUSHDOWN DONE "<<id<<' '<<lazy[id].fi.fi<<' '<<lazy[id].fi.se<<endl;
            }
        }
        void reupdate(ll id){
            tree[id] = better(tree[id<<1],tree[id<<1|1]);
        }
        void update_add(ll id,ll l,ll r,ll l1,ll r1){
            if (val[l] > r1 || l1 > val[r] || l1 > r1)return;
            if (l1 <= val[l] && val[r] <= r1){
//                cout<<"SUS "<<l<<' '<<r<<' '<<val[l]<<' '<<val[r]<<endl;
//                cout<<"BEFORE "<<tree[id].fi<<' '<<tree[id].se<<' '<<lazy[id].fi.fi<<' '<<lazy[id].fi.se<<' '<<lazy[id].se<<' '<<endl;
                push_add(id,1);
//                cout<<"AFTER "<<tree[id].fi<<' '<<tree[id].se<<' '<<lazy[id].fi.fi<<' '<<lazy[id].fi.se<<' '<<lazy[id].se<<' '<<endl;
                return;
            }
            lz(id);
            ll mid = (l + r) >> 1;
            update_add(id<<1,l,mid,l1,r1);
            update_add(id<<1|1,mid+1,r,l1,r1);
            reupdate(id);
        }
        void out_tree(ll id=1,ll l=0,ll r=sz(val)-1){
            cout<<id<<' '<<l<<' '<<r<<endl;
            cout<<tree[id].fi<<' '<<tree[id].se<<' '<<eval(tree[id],A,B)<<endl;
            cout<<"LAZY "<<lazy[id].fi.fi<<' '<<lazy[id].fi.se<<' '<<lazy[id].se<<endl<<endl;
            if (l!=r){
                ll mid=(l+r)>>1;
                out_tree(id<<1,l,mid);
                out_tree(id<<1|1,mid+1,r);
            }
        }
        void add(ll l,ll r){
            update_add(1,0,sz(val)-1,l,r);
        }
        pll best(){
            return tree[1];
        }
        void minimize(){
            pll tmp = best();
            tmp.fi++;
            lazy[1].fi = better(lazy[1].fi,tmp);
        }
    }
    vector <pll> hull;
    pll solve(ll A,ll B){
//        cout<<A<<' '<<B<<endl;
        seg::reset(A,B);
        for (ll i = 0;i < n;i ++){
//            cout<<i<<endl;
            seg::add(a[i].fi,a[i].se);
            seg::minimize();
//            cout<<"WALL "<<i<<endl;
//            seg::out_tree();
//            cout<<i<<' '<<seg::best().fi<<' '<<seg::best().se<<endl;
        }
        return seg::best();
    }
    void dnc(pll L,pll R){
//        cout<<L.fi<<' '<<L.se<<' '<<R.fi<<' '<<R.se<<endl;
        ll Ex = R.se-L.se,Ey = L.fi-R.fi;
        hull.push_back(L);
        pll mid = solve(Ex,Ey);
        if (eval(mid,Ex,Ey)!=eval(L,Ex,Ey)){
            dnc(L,mid);
            dnc(mid,R);
        }
        hull.push_back(R);
    }
}
void init(int N, int M, std::vector<int> Y1, std::vector<int> Y2)
{
    n=N;
    m=M;
    for (ll i = 0;i < n;i ++){
        a[i] = MP(Y1[i],Y2[i]);
    }
//    cout<<"DNC START"<<endl;
    seg::init_value();
    pll A1=solve(1,N),A2=solve(N,1);
    dnc(A1,A2);
    sort(hull.begin(),hull.end());
    hull.resize(unique(hull.begin(),hull.end())-hull.begin());
//    if (A1 != A2)hull.push_back(A2);
//    for (auto x:hull){
//        cout<<"HULL "<<x.fi<<' '<<x.se<<'\n';
//    }
//    cout<<"INIT SUCCEED"<<endl;
}

long long minimize(int X, int Y)
{
    ll l=1;
    ll r=sz(hull)-1;
    ll ans = 0;
    while (l<=r){
        ll mid = (l + r) >> 1;
        if (eval(hull[mid],X,Y) < eval(hull[mid-1],X,Y)){
            ans = mid;
            l = mid + 1;
        }
        else{
            r = mid - 1;
        }
    }
//    ll dp[n+1][m];
//    for (ll i = 0;i < m;i ++)dp[0][i] = 0;
//    for (ll i = 0;i < n;i ++){
//        ll min1 = 1e18;
//        for (ll j = 0;j < m;j ++){
//            dp[i+1][j] = dp[i][j];
//            if (a[i].fi<=j&&j<=a[i].se)dp[i+1][j] += Y;
//            min1 = min(min1,dp[i+1][j]);
//        }
//
//        for (ll j = 0;j < m;j ++){
//            dp[i+1][j] = min(dp[i+1][j],min1+X);
//        }
//    }
//    ll res = 1e18;
//    for (ll j = 0;j < m;j ++)res = min(res,dp[n][j]);
//    if (!(eval(hull[ans],X,Y) == res))cout<<eval(hull[ans],X,Y)<<' '<<res<<endl;
//    assert(eval(hull[ans],X,Y) == res);
    return eval(hull[ans],X,Y);
}