#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <ctime>
#include <cassert>
#include <queue>

using namespace std;

const int inf = (int)1e9;
int t[101][2];
int dp[2][101];
int n, m;

bool Ok(int needTime) {
    for (int j = 0; j <= m; ++j)
        dp[1][j] = inf;

    dp[1][m] = m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= m; ++j) {
            dp[0][j] = dp[1][j];
            dp[1][j] = inf;
        }

        for (int j = 0; j <= m; ++j) if (dp[0][j] < inf)
            for (int k = 0, curtime = 0; k <= j && curtime <= needTime; ++k, curtime += t[i][0])
                dp[1][j - k] = min(dp[1][j - k], max(0, dp[0][j] - (needTime - curtime) / t[i][1]));
        if (dp[1][0] == 0) return true;
    }
    return false;

}

void Solve() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
        scanf("%d%d", &t[i][0], &t[i][1]);
    int le = 0, ri = 50001;
    while (ri - le > 1) {
        int mid = (le + ri) >> 1;
        if (Ok(mid)) ri = mid; else
        le = mid;
    }
    printf("%d\n", ri);

}

int main() {
    #ifdef LOCAL
        freopen("in","r",stdin);
        freopen("out","w",stdout);
    #endif
    int tests;
    scanf("%d", &tests);
    for (int test = 1; test <= tests; ++test) {
        printf("Case %d: ", test);
        Solve();
    }
    return 0;
}