DS_2022_HW5_Sort

#include <bits/stdc++.h>
using namespace std;
#define INF INT64_MAX
#define ll long long
#define pll pair<ll,ll>
#define DEBUG 0

int n, m;
vector<pll> v1; //順向
vector<pll> v2; //逆向

struct Cmp1 {
    bool operator()(const pll& lhs, const pll& rhs) const{
        if(lhs.first == rhs.first){
            return lhs.second >= rhs.second;
        }
        else{
            return lhs.first > rhs.first;
        }
        
    }
};

struct Cmp2 {
    bool operator()(const pll& lhs, const pll& rhs) const{
        if(lhs.first == rhs.first){
            return lhs.second >= rhs.second;
        }
        else{
            return lhs.first > rhs.first;
        }
        
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    ll s, e;
    int j=0, k=0;
    for(int i=0; i<n; i++){
        cin >> s >> e;
        if(s<e){
            v1.push_back({s, e});
            j++;
        }
        else if(s>e){
            v2.push_back({s, e});
            k++;
        }
    }
    // 按照 Si heapify
    priority_queue<pll,vector<pll>,Cmp1> p1(v1.begin(), v1.end()); //順向
    priority_queue<pll,vector<pll>,Cmp2> p2(v2.begin(), v2.end()); //逆向

    ll dis = 0; // ans
    ll cur = 0; // cur position
    while(!p1.empty() && !p2.empty()){
        //llabs(cur-p1.top().first)
        if(cur > p1.top().first && llabs(cur-p2.top().first)+llabs(p2.top().second-p2.top().first)+llabs(p2.top().second-p1.top().first) <= llabs(cur-p1.top().first)){  
            //找看看有沒有有用的逆向的 -> 先逆向再去順向的cost <= 直接去順向cost
            if(DEBUG) cout << "Case0\n";
            pll now = p2.top(); p2.pop();
            dis += llabs(now.first - cur);
            dis += llabs(now.second - now.first);
            cur = now.second;
        }
        else if(p1.top().second <= p2.top().first){ // 順向的Ei <= 逆向的Si -> 直接順向
            
            if(DEBUG) cout << "Case1\n";
            pll now = p1.top(); p1.pop();
            dis += llabs(now.first - cur);
            dis += llabs(now.second - now.first);
            cur = now.second;            
        }
        else if(p1.top().first >= p2.top().first){ // 順向的Si >= 逆向的Si -> 直接逆向
            if(DEBUG) cout << "Case2\n";
            pll now = p2.top(); p2.pop();
            dis += llabs(now.first - cur);
            dis += llabs(now.second - now.first);
            cur = now.second;
        }
        else{ // 順向的Ei > 逆向的Si -> 搬順向到逆向的Si 然後搬逆向
            if(DEBUG) cout << "Case3\n";
            pll now1 = p1.top(); p1.pop(); // 順向
            pll now2 = p2.top(); p2.pop(); // 逆向
            dis += llabs(now1.first - cur);
            dis += llabs(now2.first - now1.first);
            dis += llabs(now2.second - now2.first);
            cur = now2.second;
            p1.push({now2.first, now1.second}); // 新的  
        }
        if(DEBUG) cout << "dis: " <<dis << " cur: "<<cur<<'\n';
    }

    while(!p1.empty()){
        if(DEBUG) cout << "Case4\n";
        pll now = p1.top(); p1.pop();
        dis += llabs(now.first - cur);
        dis += llabs(now.second - now.first);
        cur = now.second;
        if(DEBUG) cout << "dis: " <<dis << " cur: "<<cur<<'\n'; 
    }
    while(!p2.empty()){
        if(DEBUG) cout << "Case5\n";
        pll now = p2.top(); p2.pop();
        dis += llabs(now.first - cur);
        dis += llabs(now.second - now.first);
        cur = now.second;
        if(DEBUG) cout << "dis: " <<dis << " cur: "<<cur<<'\n';
    }

    // 走到m
    dis += llabs(m-cur);
    cout << dis << '\n';
    return 0;
}