#include <bits/stdc++.h> using namespace std; const int N = 2010; // 1 不返回 2 返回 long long f1[N], f2[N]; //前 i 行取 j 个的最小时间(不返回/返回) long long dp1[N][N]; long long dp2[N][N]; long long ans[N]; int n; struct node{ int x, y; bool operator < (const node& b) const { return y == b.y ? x < b.x : y < b.y; } }st[N]; inline void calc_1(int l, int r){ vector<long long> left; vector<long long> right; right.push_back(0); for(int i = l; i <= r; i++){ if(st[i].x < 0) left.push_back(abs(st[i].x)); else right.push_back(st[i].x); } left.push_back(0); reverse(left.begin(), left.end()); for(int i = 0; i <= r - l + 1; i++) f1[i] = f2[i] = 0x3f3f3f3f; for(int i = 0; i < left.size(); i++){ for(int j = 0; j < right.size(); j++){ f1[i+j] = min(f1[i+j], min(2 * left[i] + right[j], left[i] + 2 * right[j])); f2[i+j] = min(f2[i+j], 2 * (left[i] + right[j])); } } } inline void calc_2(int cnt, int num, int d, int all){ for(int i = 0; i <= all; i++){ for(int j = min(i, num); j >= 0; j--){ //返回: 上一个取 i-j, 一位取 j, 加上 y 的差值 dp2[cnt][i] = min(dp2[cnt][i], dp2[cnt-1][i-j] + f2[j] + d); dp1[cnt][i] = min(dp1[cnt][i], dp2[cnt-1][i-j] + f1[j] + d); } ans[i] = min(ans[i], dp1[cnt][i]); } } int main(){ scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%d%d", &st[i].x, &st[i].y); } sort(st + 1, st + 1 + n); memset(dp1, 0x3f, sizeof dp1); memset(dp2, 0x3f, sizeof dp2); memset(ans, 0x3f, sizeof ans); dp1[0][0] = dp2[0][0] = 0; int idx = 1; for(int i = 1; i <= n; i++){ int l = i, r = i; while(st[r].y == st[l].y) r++; r--; calc_1(l, r); calc_2(idx++, r - l + 1, st[l].y - st[l-1].y, r); i = r; } for(int i = 1; i < n; i++){ printf("%lld\n", ans[i]); } printf("%lld\n", ans[n]); return 0; }