DOMINOS

#include <iostream>
#include <algorithm>
#include <numeric>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <climits>
#include <string>
#include <cstdio>
#include <cmath>
#define task "DOMINOS"
using namespace std;
const int N = 1e3;
long long hieu[N+1], a, b, dp[N+1][14*N+1], n, tmp, j1, j2;
void read()
{
   cin >> n;
   fill(dp[0], dp[N] + 14*N+1, INT_MAX);
   for (int i = 1; i <= n; ++ i)
   {
       cin >> a >> b;
       hieu[i] = a - b;
   }
   tmp = 6*n + 6;
}
void debug()
{
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = -6*n; j <= 6*n; ++ j)
        {
            if (dp[i][j + tmp] >= INT_MAX)
            {
                cout << ' ';
            }
            else
            {
                cout << dp[i][j + tmp];
            }
            cout << ' ';
        }
        cout << '\n';
    }
}
void traceback(int x)
{
   cout << dp[n][x + tmp] << '\n';
   for (int i = n; i >= 2; -- i)
   {
       if (dp[i-1][x - hieu[i] + tmp] == dp[i][x + tmp])
       {
           x = x - hieu[i];
       }
       else
       {
           cout << i <<' ';
           x = x + hieu[i];
       }
   }
   if (dp[1][hieu[1] + tmp] != dp[1][x + tmp])
   {
       cout << 1;
   }
}
void solve()
{
   dp[1][-hieu[1] + tmp] = 1;
   dp[1][hieu[1] + tmp] = 0;
   for (int i = 2; i <= n; ++ i)
   {
       for (int j = -6*n; j <= 6*n; ++ j)
       {
           dp[i][j + tmp] = min(dp[i-1][j-hieu[i] + tmp], dp[i-1][j + hieu[i] + tmp] + 1);
       }
   }
   //debug();
   for (int j = 0; j <= 6 *n; ++ j)
   {
       if (dp[n][j + tmp] < INT_MAX)
       {
           j1 = j;
           //cout << dp[n][j1 + tmp] <<' '<<j1 << '\n';
           break;
       }
   }
   for (int j = -1; j >= -6 *n; -- j)
   {
       if (dp[n][j + tmp] < INT_MAX)
       {
           j2 = j;
           //cout << dp[n][j2 + tmp] <<' '<<j2 << '\n';
           break;
       }
   }
   if (abs(j1) < abs(j2))
   {
       traceback(j1);
   }
   else if (abs(j1) > abs(j2))
   {
       traceback(j2);
   }
   else
   {
       if (dp[n][j1 + tmp] <= dp[n][j2 + tmp])
       {
           traceback(j1);
       }
       else
       {
           traceback(j2);
       }
   }
}
int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   //freopen(task".INP", "r", stdin);
   //freopen(task".OUT", "w", stdout);
   read();
   solve();
}