Untitled

#include<iostream>
using namespace std;
const int mod = 1e9 + 7;
int W, S;


int cd(int x, int y){
  return x * 60 + y;
}
int a[10], w[10];
int ans;
bool ok = 0;
void dfs(int p, int minW, int t, int s){
  if (s == 0){
    ans = min(ans, t);
    return;
  }     
  if (t >= ans) return;
  if (p == 5) return;
  for (int i = 0; i <= s; i++){
    if (minW + w[p] * i <= W){
      dfs(p + 1, minW + w[p] * i, t + a[p] * i, s - i);
    }
  }
}

void solve(int test){
  cin >> W >> S;
  for (int i = 0; i < 5; i++){
    int u, v; cin >> u >> v >> w[i];
    a[i] = cd(u, v);
  }
  ans = 1e9;
  dfs(0, 0, 0, S);
  cout << "Case #" << test << '\n';
  if (ans == 1e9) cout << -1 << '\n';
  else {
    cout << ans / 60 << ' ' << ans % 60 << '\n';
  }
}

int32_t main(){
  ios_base::sync_with_stdio(false), cin.tie(0);
  freopen("file1.txt", "r", stdin);
  int t = 1;
  cin >> t;
  for (int i = 1; i <= t; i++) solve(i);


}