IAogICAgI2luY2x1ZGUgJmx0O2JpdHMvc3RkYysrLmgmZ3Q7CiAgICAKICAgIHVzaW5nIG5hbWVzcGFjZSBzdGQ7CgogICAgdXNpbmcgbGwgPSBsb25nIGxvbmc7CiAgICBjb25zdCBpbnQgTU9EID0gMTAwMDAwMDAwNzsgCiAgICBjb25zdCBpbnQgTU9EMiA9ICA5OTgyNDQzNTM7IAogICAgY29uc3QgbGwgSU5GID0gMWUxODsKICAgIGNvbnN0IGludCBNWCA9IDEwMDAwMDE7IC8vY2hlY2sgdGhlIGxpbWl0cywgZHVtbXkKCgogICAgbGwgbW9kRXhwKGxsIGJhc2UsIGxsIHBvd2VyKSB7CiAgICAgICAgaWYgKHBvd2VyID09IDApIHsKICAgICAgICAgICAgcmV0dXJuIDE7CiAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgbGwgY3VyID0gbW9kRXhwKGJhc2UsIHBvd2VyIC8gMik7IGN1ciA9IGN1ciAqIGN1cjsgY3VyID0gY3VyICUgTU9EOwogICAgICAgICAgICBpZiAocG93ZXIgJSAyID09IDEpIGN1ciA9IGN1ciAqIGJhc2U7CiAgICAgICAgICAgIGN1ciA9IGN1ciAlIE1PRDsKICAgICAgICAgICAgcmV0dXJuIGN1cjsKICAgICAgICB9CiAgICB9CgogICAgbGwgaW52KGxsIGJhc2UpIHsKICAgICAgICByZXR1cm4gbW9kRXhwKGJhc2UsIE1PRC0yKTsKICAgIH0KCgogICAgbGwgbXVsKGxsIEEsIGxsIEIpIHsKICAgICAgICByZXR1cm4gKEEqQiklTU9EOwogICAgfQoKICAgIGxsIGFkZChsbCBBLCBsbCBCKSB7CiAgICAgICAgcmV0dXJuIChBK0IpJU1PRDsKICAgIH0KICAgIAogICAgbGwgZHZkKGxsIEEsIGxsIEIpIHsKICAgICAgICByZXR1cm4gbXVsKEEsIGludihCKSk7CiAgICB9CgogICAgbGwgc3ViKGxsIEEsIGxsIEIpIHsKICAgICAgICByZXR1cm4gKEEtQitNT0QpJU1PRDsKICAgIH0KCiAgICBsbCogZmFjcyA9IG5ldyBsbFtNWF07CiAgICBsbCogZmFjSW52cyA9IG5ldyBsbFtNWF07CgogICAgbGwgY2hvb3NlKGxsIGEsIGxsIGIpIHsKICAgICAgICBpZiAoYiAmZ3Q7IGEpIHJldHVybiAwOwogICAgICAgIGlmIChhICZsdDsgMCkgcmV0dXJuIDA7CiAgICAgICAgaWYgKGIgJmx0OyAwKSByZXR1cm4gMDsKICAgICAgICBsbCBjdXIgPSBmYWNzW2FdOwogICAgICAgIGN1ciA9IG11bChjdXIsIGZhY0ludnNbYl0pOwogICAgICAgIGN1ciA9IG11bChjdXIsIGZhY0ludnNbYS1iXSk7CiAgICAgICAgcmV0dXJuIGN1cjsKICAgIH0KCiAgICB2b2lkIGluaXRGYWNzKCkgewogICAgICAgIGZhY3NbMF0gPSAxOyAKICAgICAgICBmYWNJbnZzWzBdID0gMTsKICAgICAgICBmb3IgKGludCBpID0gMSA7IGkgJmx0OyBNWCA7IGkgKysgKSB7CiAgICAgICAgICAgIGZhY3NbaV0gPSAoZmFjc1tpLTFdICogaSkgJSBNT0Q7CiAgICAgICAgICAgIGZhY0ludnNbaV0gPSBpbnYoZmFjc1tpXSk7CiAgICAgICAgfQogICAgfQogICAgY29uc3QgaW50IG1heG0gPSA0MDA1OyAKICAgIGludCBuOwogICAgaW50IGlkW21heG1dW21heG1dOwogICAgaW50IGRwW21heG1dW21heG1dOwogICAgaW50IHZpc1ttYXhtXVttYXhtXTsKICAgIHZlY3RvciZsdDtpbnQmZ3Q7IGdsW21heG1dOwogICAgaW50IGRmcyhpbnQgbCwgaW50IHIpIHsKICAgICAgICBpZiAobCAmZ3Q7PXIgKSB7CiAgICAgICAgICAgIHJldHVybiAwOwogICAgICAgIH0gIAogICAgICAgIGlmIChkcFtsXVtyXSAhPSAtMSkgewogICAgICAgICAgICByZXR1cm4gZHBbbF1bcl07IAogICAgICAgIH0KICAgICAgICBkcFtsXVtyXSA9IGRmcyhsICsgMSwgcik7CiAgICAgICAgZm9yIChpbnQgbnIgOiBnbFtsXSkgewogICAgICAgICAgICBpZiAobnIgJmx0OyByKSB7CiAgICAgICAgICAgICAgICBpZiAoZHBbbF1bcl0gJmx0OyBkZnMobCxuciApICsgMSArIGRmcyhucixyKSkgewogICAgICAgICAgICAgICAgICAgIGRwW2xdW3JdID0gZGZzKGwsbnIgKSArIDEgKyBkZnMobnIscik7IAogICAgICAgICAgICAgICAgICAgIHZpc1tsXVtyXSA9IG5yOyAKICAgICAgICAgICAgICAgIH0gCiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgICAgIAogICAgICAgIAogICAgICAgIHJldHVybiBkcFtsXVtyXSArPSAoaWRbbF1bcl0gIT0gLTEgPyAxIDogMCk7IAogICAgfQogICAgCgoKICAgIHZvaWQgb3V0cHV0KGludCBsICwgaW50IHIgKSB7CiAgICAgICAgaWYgKGwgJmd0Oz0gcikgewogICAgICAgICAgICByZXR1cm47IAogICAgICAgIH0KICAgICAgICBpZiAoaWRbbF1bcl0gIT0gLTEpIHsKICAgICAgICAgICAgY291dCAmbHQ7Jmx0OyBpZFtsXVtyXSAmbHQ7Jmx0OyAnICc7ICAKICAgICAgICB9IAogICAgICAgIGlmICh2aXNbbF1bcl0gPT0gLTEpIHsKICAgICAgICAgICAgb3V0cHV0KGwgKyAxLCByKTsKICAgICAgICB9IGVsc2V7CiAgICAgICAgICAgIGNvdXQgJmx0OyZsdDsgaWRbbF1bdmlzW2xdW3JdXSAmbHQ7Jmx0OyAnICc7CiAgICAgICAgICAgIG91dHB1dChsLHZpc1tsXVtyXSk7CiAgICAgICAgICAgIG91dHB1dCh2aXNbbF1bcl0scik7CiAgICAgICAgfQogICAgfQogICAgaW50IG1haW4oKSAgewogICAgICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7IGNpbi50aWUoMCk7ICAKICAgICAgICBjaW4gJmd0OyZndDsgbjsgCiAgICAgICAgbWVtc2V0KGlkLCAtMSwgc2l6ZW9mKGlkKSk7IAogICAgICAgIG1lbXNldChkcCwgLTEsIHNpemVvZihkcCkpOyAKICAgICAgICBtZW1zZXQodmlzLCAtMSwgc2l6ZW9mKHZpcykpOyAKICAgICAgICBpbnQgYyA9IDA7CiAgICAgICAgdmVjdG9yJmx0O2ludCZndDsgczsKICAgICAgICB2ZWN0b3ImbHQ7cGFpciZsdDtpbnQsaW50Jmd0OyZndDsgcChuKTsKICAgICAgICBmb3IgKGludCBpID0gMSA7IGkgJmx0Oz0gbjsgaSArKykgewogICAgICAgICAgICBpbnQgYyAsZCA7IGNpbiAmZ3Q7Jmd0OyBjICZndDsmZ3Q7IGQ7CiAgICAgICAgICAgIGludCBhID0gIGMgLSBkOwogICAgICAgICAgICBpbnQgIGIgPSBjICsgZDsgCiAgICAgICAgICAgIHMucHVzaF9iYWNrKGEpOwogICAgICAgICAgICBzLnB1c2hfYmFjayhiKTsKICAgICAgICAgICAgcFtpXS5maXJzdCA9IGE7CiAgICAgICAgICAgIHBbaV0uc2Vjb25kID0gYjsKICAgICAgICB9CiAgICAgICAgc29ydChzLmJlZ2luKCkgLCBzLmVuZCgpKTsgCiAgICAgICAgYXV0byBpdCA9IHVuaXF1ZShzLmJlZ2luKCksIHMuZW5kKCkpOwogICAgICAgIHMuZXJhc2UoaXQscy5lbmQoKSk7CiAgICAgICAgaW50IHUgPSBzLnNpemUoKTsgCiAgICAgICAgbWFwJmx0O2ludCxpbnQmZ3Q7IG07CiAgICAgICAgZm9yIChpbnQgaSA9IDEgOyBpICZsdDs9IHUgIDsgaSArKykgewogICAgICAgICAgICBtW3NbaSAtIDFdXSA9IGk7ICAKICAgICAgICB9CiAgICAgICAgZm9yIChpbnQgaSA9IDAgaSAmbHQ7IG47IGkgKyspIHsKICAgICAgICAgICAgcFtpXS5maXJzdCA9IG1bcFtpXS5maXJzdF07CiAgICAgICAgICAgIHBbaV0uc2Vjb25kPSBtW3BbaV0uc2Vjb25kXTsKICAgICAgICAgICAgZ2xbcFtpXS5maXJzdF0ucHVzaF9iYWNrKHBbaV0uc2Vjb25kKTsgCiAgICAgICAgICAgIGlkW3BbaV0uZmlyc3RdW3BbaV0uc2Vjb25kXSA9IGkgKyAxOyAKICAgICAgICB9CiAgICAgICAgY291dCAmbHQ7Jmx0OyBkZnMoMSx1KSAmbHQ7Jmx0OyBlbmRsOyAKICAgICAgICBvdXRwdXQoMSx1KTsKICAgICAgICByZXR1cm4gMDsKICAgIH0KICAgIA==
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1000000007;
const int MOD2 = 998244353;
const ll INF = 1e18;
const int MX = 1000001; //check the limits, dummy
ll modExp(ll base, ll power) {
if (power == 0) {
return 1;
} else {
ll cur = modExp(base, power / 2); cur = cur * cur; cur = cur % MOD;
if (power % 2 == 1) cur = cur * base;
cur = cur % MOD;
return cur;
}
}
ll inv(ll base) {
return modExp(base, MOD-2);
}
ll mul(ll A, ll B) {
return (A*B)%MOD;
}
ll add(ll A, ll B) {
return (A+B)%MOD;
}
ll dvd(ll A, ll B) {
return mul(A, inv(B));
}
ll sub(ll A, ll B) {
return (A-B+MOD)%MOD;
}
ll* facs = new ll[MX];
ll* facInvs = new ll[MX];
ll choose(ll a, ll b) {
if (b > a) return 0;
if (a < 0) return 0;
if (b < 0) return 0;
ll cur = facs[a];
cur = mul(cur, facInvs[b]);
cur = mul(cur, facInvs[a-b]);
return cur;
}
void initFacs() {
facs[0] = 1;
facInvs[0] = 1;
for (int i = 1 ; i < MX ; i ++ ) {
facs[i] = (facs[i-1] * i) % MOD;
facInvs[i] = inv(facs[i]);
}
}
const int maxm = 4005;
int n;
int id[maxm][maxm];
int dp[maxm][maxm];
int vis[maxm][maxm];
vector<int> gl[maxm];
int dfs(int l, int r) {
if (l >=r ) {
return 0;
}
if (dp[l][r] != -1) {
return dp[l][r];
}
dp[l][r] = dfs(l + 1, r);
for (int nr : gl[l]) {
if (nr < r) {
if (dp[l][r] < dfs(l,nr ) + 1 + dfs(nr,r)) {
dp[l][r] = dfs(l,nr ) + 1 + dfs(nr,r);
vis[l][r] = nr;
}
}
}
return dp[l][r] += (id[l][r] != -1 ? 1 : 0);
}
void output(int l , int r ) {
if (l >= r) {
return;
}
if (id[l][r] != -1) {
cout << id[l][r] << ' ';
}
if (vis[l][r] == -1) {
output(l + 1, r);
} else{
cout << id[l][vis[l][r]] << ' ';
output(l,vis[l][r]);
output(vis[l][r],r);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
memset(id, -1, sizeof(id));
memset(dp, -1, sizeof(dp));
memset(vis, -1, sizeof(vis));
int c = 0;
vector<int> s;
vector<pair<int,int>> p(n);
for (int i = 1 ; i <= n; i ++) {
int c ,d ; cin >> c >> d;
int a = c - d;
int b = c + d;
s.push_back(a);
s.push_back(b);
p[i].first = a;
p[i].second = b;
}
sort(s.begin() , s.end());
auto it = unique(s.begin(), s.end());
s.erase(it,s.end());
int u = s.size();
map<int,int> m;
for (int i = 1 ; i <= u ; i ++) {
m[s[i - 1]] = i;
}
for (int i = 0 i < n; i ++) {
p[i].first = m[p[i].first];
p[i].second= m[p[i].second];
gl[p[i].first].push_back(p[i].second);
id[p[i].first][p[i].second] = i + 1;
}
cout << dfs(1,u) << endl;
output(1,u);
return 0;
}