GRD3-T03: Railroad

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

typedef long long lli;
typedef pair<int, int> pii;

const int N = 16;

int nRail;
pii rail[N + 10];
vector<vector<lli>> dp(N + 1, vector<lli>((1 << N) + 1, -1));

lli shortAddition(int st, int chosen){
    if(chosen == 0){
        return 0;
    }
    if(dp[st][chosen] != -1){
        return dp[st][chosen];
    }
    lli mn = 1e18;
    for(int i = 1; i <= nRail; ++i){
        if((chosen & (1 << (i - 1))) != 0){
            lli add = 0;
            if(rail[st].second > rail[i].first){
                add = rail[st].second - rail[i].first;
            }
            mn = min(mn, add + shortAddition(i, chosen & (~(1 << (i - 1)))));
        }
    }
    return dp[st][chosen] = mn;
}

int main(){

    scanf("%d", &nRail);
    for(int i = 1; i <= nRail; ++i){
        scanf("%d %d", &rail[i].first, &rail[i].second);
    }
    lli mn = 1e18;
    for(int i = 1; i <= nRail; ++i){
        mn = min(mn, shortAddition(i, ((1 << nRail) - 1) & ~(1 << (i - 1))));
    }
    cout << mn;

    return 0;
}