1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 #include "set"
13 #include "utility"
14 using namespace std;
15 typedef pair<int, int> pii;
16 #define pb push_back
17 #define mp make_pair
18 #define fi first
19 #define se second
20 #define sof(x) sizeof(x)
21 #define lc(x) (x << 1)
22 #define rc(x) (x << 1 | 1)
23 #define lowbit(x) (x & (-x))
24 #define ll long long
25 #define MAX 110
26 const int inf = 1 << 29;
27 int dp[MAX][MAX][3];
28 int sum[MAX][MAX];
29 int n, m;
30 void solve() {
31     memset(dp, 0, sof(dp));
32     int ans = 0;
33     for(int i = 1; i <= n; i++) {
34         for(int j = 1; j <= m; j++) {
35             for(int k = 1; k <= j; k++) {
36                 if(k & 1) {
37                     dp[i][j][1] = max(dp[i][j][1], dp[i-1][j-k][0] + sum[i][k]);
38                     dp[i][j][1] = max(dp[i][j][1], dp[i-1][j-k][1] + sum[i][k]);
39                 } else {
40                     dp[i][j][0] = max(dp[i][j][0], dp[i-1][j-k][0] + sum[i][k]);
41                     dp[i][j][2] = max(dp[i][j][2], dp[i-1][j-k][1] + sum[i][k]);
42                     dp[i][j][2] = max(dp[i][j][2], dp[i-1][j-k][2] + sum[i][k]);
43                 }
44             }
45         }
46         ans = max(ans, max(dp[i][m][0], max(dp[i][m][1], dp[i][m][2])));
47     }
48     cout << ans << endl;
49 }
50 
51 int main() {
52     int T, Case = 1;
53     cin >> T;
54     int a, b;
55     while(T--) {
56         cin >> n >> m;
57         for(int i = 1; i <= n; i++) {
58             cin >> a >> b;
59             for(int j = 1; j <= m; j++) {
60                 sum[i][j] = a * j - j * (j - 1) * b / 2;
61             }
62         }
63         printf("Case #%d: ", Case++);
64         solve();
65     }
66     return 0;
67 }
68