#include <bits/stdc++.h>
using namespace std;
class bipartiteGraph {
 public:
  int n;
  vector<vector<int>> cost;
  vector<int> mx, my, lx, ly, p;
  vector<bool> vx, vy;
  vector<int> dy, pdy;
  queue<int> qu{};
  int MAX{numeric_limits<int>::max()};
  bipartiteGraph(int n)
      : n(n),
        cost(n, vector<int>(n)),
        mx(n, -1),
        my(n, -1),
        lx(n),
        ly(n),
        p(n),
        vx(n),
        vy(n),
        dy(n),
        pdy(n) {}
  bool DFS(int x) {
    vx[x] = true;
    for (int y{0}; y < n; ++y)
      if (!vy[y] && lx[x] + ly[y] == cost[x][y]) {
        vy[y] = true;
        if (my[y] == -1 || DFS(my[y])) {
          mx[x] = y, my[y] = x;
          return true;
        }
      }
    return false;
  }
  int Hungarian() {
    for (int i{0}; i < n; ++i) {
      lx[i] = ly[i] = 0;
      for (int j{0}; j < n; ++j)
        if (cost[i][j] != MAX) lx[i] = max(lx[i], cost[i][j]);
      mx[i] = my[i] = -1;
    }
    for (int x{0}; x < n; ++x) {
      while (true) {
        fill(vx.begin(), vx.end(), false);
        fill(vy.begin(), vy.end(), false);
        if (DFS(x)) break;
        int d{MAX};
        for (int x{0}; x < n; ++x)
          if (vx[x])
            for (int y{0}; y < n; ++y)
              if (!vy[y] && cost[x][y] != MAX)
                d = min(d, lx[x] + ly[y] - cost[x][y]);
        if (d == MAX) return -MAX;
        for (int x{0}; x < n; ++x)
          if (vx[x]) lx[x] -= d;
        for (int y{0}; y < n; ++y)
          if (vy[y]) ly[y] += d;
      }
    }
    for (int x{0}; x < n; ++x)
      for (int y{0}; y < n; ++y)
        if (lx[x] + ly[y] < cost[x][y]) {
          cout << "Err1!! " << lx[x] << ' ' << ly[y] << ' ' << cost[x][y]
               << endl;
        }
    for (int x{0}; x < n; ++x)
      if (lx[x] + ly[mx[x]] != cost[x][mx[x]]) cout << "Err2!!" << endl;
    for (int y{0}; y < n; ++y)
      if (lx[my[y]] + ly[y] != cost[my[y]][y]) cout << "Err3!!" << endl;
    int weight{0};
    for (int x{0}; x < n; ++x) weight += cost[x][mx[x]];
    return weight;
  }
};
void solve() {
  int n, k;
  cin >> n >> k;
  bipartiteGraph bg(n);
  for (int i{0}; i < n; ++i) {
    int a, b;
    cin >> a >> b;
    for (int j{0}; j < n; ++j)
      bg.cost[i][j] = a * (j < k - 1 || j == n - 1) + b * min(j, k - 1);
  }
  cout << bg.Hungarian() << '\n';
  bg.Hungarian();
  cout << n + (n - k) << '\n';
  for (int y{0}; y < n; ++y) {
    cout << bg.my[y] + 1 << ' ';
    if (y >= k - 1 && y != n - 1) cout << -1 * (bg.my[y] + 1) << ' ';
  }
  cout << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
  int n;
  cin >> n;
  bipartiteGraph bg(n);
  for (int i{0}; i < n; ++i)
    for (int j{0}; j < n; ++j) cin >> bg.cost[i][j], bg.cost[i][j] *= -1;
  cout << bg.Hungarian() << endl;
  for (auto& y : bg.mx) cout << y << ' ';
  cout << endl;
  return 0;
}
