题意：长度为L的金条，将n根金棍尽可能放上去，要求重心在L上，使得价值最大，最多有两条可以长度折半的放上去。
分析：首先长度可能为奇数，先*2。然后除了两条特殊的金棍就是01背包，所以dp[now][j][k]表示当前状态，长度为j，使用了k条特殊金棍获得的最大价值，需要对内存和时间优化。
/************************************************
* Author :Running_Time
* Created Time :2015/10/21 星期三 11:55:40
* File Name :D.cpp
************************************************/
#include <bits/stdc++.h>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e3 + 10;
const int L = 4e3 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
ll dp[2][L][3];
struct P {
int a;
ll v;
}p[N]; ll Max(ll a, ll b) {
return a > b ? a : b;
} int main(void) {
int T, cas = 0; scanf ("%d", &T);
while (T--) {
int n, l; scanf ("%d%d", &n, &l);
l *= 2;
ll ans = 0;
for (int i=1; i<=n; ++i) {
scanf ("%d%lld", &p[i].a, &p[i].v);
p[i].a *= 2;
ans = max (ans, p[i].v);
}
memset (dp, 0, sizeof (dp));
int now = 1;
for (int i=1; i<=n; ++i) {
now = 1 - now;
for (int j=0; j<=l; ++j) {
for (int k=0; k<3; ++k) {
dp[now][j][k] = dp[1-now][j][k];
}
}
for (int j=l; j>=p[i].a/2; --j) {
for (int k=0; k<3; ++k) {
if (j >= p[i].a) dp[now][j][k] = max (dp[now][j][k], dp[1-now][j-p[i].a][k] + p[i].v);
if (k) dp[now][j][k] = max (dp[now][j][k], dp[1-now][j-p[i].a/2][k-1] + p[i].v);
}
}
for (int i=0; i<2; ++i) {
for (int j=0; j<=l; ++j) {
for (int k=0; k<3; ++k) ans = max (ans, dp[i][j][k]);
}
}
}
printf ("Case #%d: %lld\n", ++cas, ans);
} return 0;
}