기지국

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<utility>
using namespace std;

typedef pair<int, int> PAIR;
#define X first
#define Y second

int n;
PAIR b[10005];
int d[10005];


int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d %d", & b[i].X, &b[i].Y);
        if(b[i].Y < 0)
        {
            b[i].Y = -b[i].Y;
        }
    }

    sort(b, b + n );

    d[0] = b[0].Y * 2;
    for(int i = 1; i < n ; i++){
        int mx_height = b[i].Y;
        d[i] = d[i-1] + b[i].Y *2;
        for(int j = i-1; j>= 0; j--){
            mx_height = max(mx_height, b[j].Y);
            if(j > 0){
                d[i] = min(d[i], max(2 * mx_height, b[i].X- b[j].X)+d[j - 1]);

            } else
                d[i] = min(d[i], max(2* mx_height, b[i].X - b[j].X));
        }

    }
    printf("%d", d[n-1]);

    return 0;
}

DP 문제, 어려웠음 생각의 전환이 필요한듯..