#include <bits/stdc++.h>
using namespace std;
using namespace std;
const int maxn = 1048576;
const int mod = 998244353;
const double pi = acos(-1);
int dp[77][77], from[77][77];
bool update(int &x, int v) {
  if (x < v) {
    x = v;
    return 1;
  }
  return 0;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> dp[0][0];
  int n, k;
  while (cin >> n >> k) {
    vector<pair<pair<int, int>, int>> pp;
    for (int i = 0; i < n; i++) {
      int x, y;
      cin >> x >> y;
      pp.push_back({{y, x}, i + 1});
    }
    sort(pp.begin(), pp.end());
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < 76; i++) {
      for (int j = 0; j < 76; j++) {
        from[i][j] = 1;
      }
    }
    dp[0][0] = 0;
    for (int i = 0; i < (int)pp.size(); i++) {
      for (int j = 0; j <= min(k, i); j++) {
        if (j < k) {
          if (update(dp[j + 1][i - j], dp[j][i - j] + pp[i].first.second +
                                           pp[i].first.first * j)) {
            from[j + 1][i - j] = 0;
          }
        }
        if (update(dp[j][i - j + 1],
                   dp[j][i - j] + pp[i].first.first * (k - 1))) {
          from[j][i - j + 1] = 1;
        }
      }
    }
    int now = k;
    vector<int> res[2];
    for (int i = (int)pp.size(); i > 0; i--) {
      cout << now << ' ' << i << endl;
      res[from[now][i - now]].push_back(pp[i - 1].second);
      if (!from[now][i - now]) {
        now--;
      }
    }
    reverse(res[0].begin(), res[0].end());
    vector<int> ans;
    for (int i = 0; i < (int)res[0].size() - 1; i++) {
      ans.push_back(res[0][i]);
    }
    for (auto &i : res[1]) {
      ans.push_back(i);
      ans.push_back(-i);
    }
    ans.push_back(res[0].back());
    cout << (int)ans.size() << '\n';
    for (auto &i : ans) {
      cout << i << ' ';
    }
    cout << '\n';
  }
}
