#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
const long long int N = 5001;
const long long int p = 31;
const long long int INF = 1e9;
const long long int mod = 1e9;
long long int powm(long long int a, long long int b) {
  a = a % mod;
  long long int res = 1;
  while (b) {
    if (b & 1) res = (res * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return (res % mod);
}
long long int a[N], b[N];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long int t = 1;
  cin >> t;
  while (t--) {
    long long int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
      cin >> a[i] >> b[i];
    }
    long long int arr[n + 1][n + 1];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (j < k - 1) {
          arr[i][j] = INF - (a[i] + (j)*b[i]);
        } else if (j == n - 1) {
          arr[i][j] = INF - (a[i] + (k - 1) * b[i]);
        } else {
          arr[i][j] = INF - ((k - 1) * b[i]);
        }
      }
    }
    long long int m = n;
    vector<int64_t> u(n + 1), v(m + 1);
    vector<int> p(m + 1), way(m + 1);
    for (int i = 1; i <= n; i++) {
      vector<int64_t> min_v(m + 1, INF);
      vector<bool> used(m + 1, false);
      p[0] = i;
      int j0 = 0;
      do {
        used[j0] = true;
        int i0 = p[j0], j1 = 0;
        int64_t delta = INF;
        for (int j = 1; j <= m; j++)
          if (!used[j]) {
            int64_t cur = arr[i0 - 1][j - 1] - u[i0] - v[j];
            if (cur < min_v[j]) {
              min_v[j] = cur;
              way[j] = j0;
            }
            if (min_v[j] < delta) {
              delta = min_v[j];
              j1 = j;
            }
          }
        for (int j = 0; j <= m; j++)
          if (used[j]) {
            u[p[j]] += delta;
            v[j] -= delta;
          } else {
            min_v[j] -= delta;
          }
        j0 = j1;
      } while (p[j0] != 0);
      do {
        int j1 = way[j0];
        p[j0] = p[j1];
        j0 = j1;
      } while (j0 != 0);
    }
    vector<long long int> ans(n + 1);
    for (long long int j = 1; j <= m; ++j) ans[p[j]] = j;
    long long int ct = 0;
    cout << n + (n - k) << '\n';
    for (long long int i = 1; i <= n; i++) {
      cout << p[i] << " ";
      ct++;
      if (ct == k && i != n) {
        cout << -p[i] << " ";
        ct--;
      }
    }
    cout << '\n';
  }
}
