#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define EPS 1e-11
#define target 666

int N, X;
int C[10], M[10];
int minTimes[10];
double ipw[30];
unsigned int visited[32768];
double maxEfficiency[1024], sumM[1024];
double res;

void solve(double Effort, double Magical, int mask, int mask2){
  int i,j,k;
  int can;
  double NextEffort, NextMagical;

  if(visited[mask/32] & 1u<<(mask%32)) return;
  visited[mask/32] |= 1u<<(mask%32);

  if(Effort + (target - Magical) / maxEfficiency[mask2] > res) return;
  if(Magical + sumM[mask2] < 666-EPS) return;

  can = (int)((Magical+EPS) / X);

  rep(i,N) if(!(mask2&1<<i)){
    if(can <minTimes[i]){
      NextEffort  = Effort  + C[i] * ipw[can];
      NextMagical = Magical + M[i] * ipw[can] - can*X;
      if(target < NextMagical + EPS){
        if(res > NextEffort) res = NextEffort;
      }
      continue;
    }

    rep(k,4){
      if(minTimes[i]+k-1 > can) break;
      if(minTimes[i]+k-1 < 0) continue;
      NextEffort  = Effort  + C[i] * ipw[minTimes[i]+k-1];
      NextMagical = Magical + M[i] * ipw[minTimes[i]+k-1] - (minTimes[i]+k-1)*X;
      if(NextMagical < Magical + EPS) break;
      if(target < NextMagical + EPS){
        if(res > NextEffort) res = NextEffort;
        continue;
      }
      solve(NextEffort, NextMagical, mask+(1<<(2*i))*k, mask2+(1<<i));
    }
  }
}

int main(){
  int i, j, k;
  int T;
  double sum, fst;

  ipw[0] = 1;
  REP(i,1,30) ipw[i] = ipw[i-1] / 3;

  scanf("%d",&T);
  while(T--){
    scanf("%d%d",&N,&X);
    rep(i,N) scanf("%d%d",C+i,M+i);

    sum = 0;
    rep(i,N) sum += M[i];
    if(target > sum+EPS){ puts("impossible"); continue; }

    fst = 0;
    k = 0;
    rep(i,N){
      if(M[i]==0) continue;
      if(C[i]==0){ fst += M[i]; continue; }
      C[k] = C[i];
      M[k] = M[i]; k++;
    }
    N = k;

    if(fst > target - EPS){ puts("0"); continue; }

    rep(i,N){
      double tmp = M[i], use = 0;
      minTimes[i] = 0;
      while(tmp - use > target-EPS) tmp /= 3, use += X, minTimes[i]++;
    }

    rep(i,1<<N){
      double mx = 0, tmp;
      rep(j,N) if(!(i&1<<j)){
        tmp = M[j] / (double)C[j];
        if(mx < tmp) mx = tmp;
      }
      maxEfficiency[i] = mx;
    }

    rep(i,1<<N){
      sumM[i] = 0;
      rep(j,N) if(!(i&1<<j)) sumM[i] += M[j];
    }

    res = 1e100;
    rep(i,32768) visited[i] = 0;
    solve(0, fst, 0, 0);
    printf("%.f\n",res);
  }

  return 0;
}