背包变形。与普通的背包问题不同的是：允许有两个物品可以花费减半。
因此加一维即可，dp[i][j][k]表示前i个物品，有j个花费减半了，总花费为k的情况下的最优解。
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0),eps=1e-;
void File()
{
freopen("D:\\in.txt","r",stdin);
freopen("D:\\out.txt","w",stdout);
}
inline int read()
{
char c = getchar(); while(!isdigit(c)) c = getchar();
int x = ;
while(isdigit(c)) { x = x * + c - ''; c = getchar(); }
return x;
} int T,n,L;
LL f[][][];
struct X{int a;LL v;}s[]; int main()
{
scanf("%d",&T); int cas=; while(T--)
{
scanf("%d%d",&n,&L); L=L*; LL ans=;
for(int i=;i<=n;i++)
{
scanf("%d%lld",&s[i].a,&s[i].v);
s[i].a=s[i].a*;
ans=max(ans,s[i].v);
}
memset(f,,sizeof f); int p=;
for(int i=;i<=n;i++)
{
p=p^;
for(int j=;j<=;j++)
{
for(int c=;c<=L;c++)
{
f[p][j][c]=f[p^][j][c];
if(c-s[i].a>=) f[p][j][c]=max(f[p][j][c],f[p^][j][c-s[i].a]+s[i].v);
if(j->=&&c-s[i].a/>=) f[p][j][c]=max(f[p][j][c],f[p^][j-][c-s[i].a/]+s[i].v);
ans=max(ans,f[p][j][c]);
}
}
}
printf("Case #%d: %lld\n",cas++,ans);
}
return ;
}