Once upon a time, there lived Catherine Ironfist, the Queen of Enroth. One day, she received the news of her father‘s death. So she sailed for Erathia to attend her father‘s funeral. Fearing the worst, she assembled a military fleet as her escort. On reaching
the coast of Erathia, Catherine found an allied wizard‘s tower, devastated from battle and abandoned. There she learned that a black-hearted knight poisoned her father using a goblet of wine, and Erathia was falling to the enemies. And then, she mustered local
armies, and marched to Erathia‘s castle, restoring lost land along the way.
During the battles, she found that the equipments for the soldiers were in urgent need. And she knew clearly that the best equipments were made by the battle dwarf‘s workshop in the world. The workshop‘s equipments were well known for the firmness and top-quality.
"Cloak of the Undead King", "Armor of the Damned", "Angelic Helm" are the nonesuch ones. But unfortunately, the workshop was seated at the Erathia‘s castle, the territory under the enemy‘s control. So she sent a brave volunteer to come into the castle and
asked for the workshop‘s help.
"It‘s our pleasure to help the righteous heroine." Rion, the leader of the workshop sent the message to Catherine, " We haven‘t enough resources to build the nonesuch equipments. So we‘ll try to offer the ordinary equipments as more as possible. Still, those
ones are much better the equipments made by other workshops. But we have faced a difficult problem. The castle is in a state of siege. The guards prohibited the equipments to be carried away from the castle. We have to ask for the trade caravans‘ help. As
you know, each trade caravan‘s capability of carrying equipments is limited. If they had carried a little more, they would be detected by the guards, which would lead them into the *. So you have to arrange how to carry these equipments."
The workshop would offer helms, armors and boots. These three ones had different defend capabilities. Also, their weight and size were different from each other. What‘s more, Rion had told Catherine that if armed with those three ones together, they would form
a set of equipments, which might provide much more defend capability. As far as the trade caravan was concerned, each one had its special weight limitation and size limitation. Catherine had to make the decision on how to arrange the transportation plan to
provide her soldiers as more defend capabilities as possible. Could you help her to finish the plan?
Input
The input describes several test cases. The first line of input for each test case contains a single integer n, the number of trade caravans (0 <= n <= 100).
The following four lines describe the information of those equipments. The first line contains three integers w1, s1 and d1, indicating the weight, size and defend capabilities of the helm. The integers w2, s2 and d2 in the second line represent the weight,
size and defend capabilities of the armor. Also, in the third line, w3, s3 and d3 are the weight, size and defend capabilities of the boot. The fourth line contains four integers c1, c2, c3 and d4. Among those integers, c1, c2, c3 are the number of helms,
armors and boots in a set of equipments, d4 is the capability of this set.
In the test case, following those data are n lines, describing the carrying capabilities of the trade caravans. Each line contains two integers, xi and yi, indicating the weight limit and size limit of a trade caravan.
The input is terminated by a description starting with n = 0. This description should not be processed.
Note: Because of the trade caravans‘ carrying capabilities, you may assume the quantities of the helms, armors and boots will not exceed 500 respectively.
Output
Your program must compute the defend capability of the best carrying plan. That is, after having performed the carrying plan, the defend capability of the equipments which have been carried away from the castle should be the largest. For each test case in the
input file, print the case number and a colon, and then the defend capability of those equipments.
Print a blank line between test cases.
Sample Input
3
1 1 3
5 6 10
2 1 2
1 1 1 50
1 1
5 6
2 1
0
Output for the Sample Input
Case 1: 50
题意：
给出3种装备A、B、C（数量不限），每种装备有weight、size和defend属性，如果这三种装备按照（c1，c2，c3）的数量组合能产生更大的defend。给出n个背包，背包有weight、size属性，问用这n个背包怎样将装这三种装备，使得产生的总defend最大。（这n个背包最多装500个单件物品）
思路：
先找状态，有10s，故状态稍稍大一点也能接受。确定了三种装备的个数的话就能确定总defend了，所以状态可以不考虑defend。那么有
dp[k][i][j]-前k个背包装i个A装备，j个B装备时最多能装的C装备。
方程：
dp[k][i][j]=max(dp[k-1][i-x][j-y]+z); （x、y、z为第k个背包能装的组合）
然后用状态算出defend就够了。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 205
#define MAXN 200005
#define mod 1000000009
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;
int n,m,ans,cnt,tot,flag;
int w[4],s[4],d[4],c[4],dd;
int dp[505][505];
struct Node
{
int x,y,z;
} cur;
vector<Node>v[105];
void solve()
{
int i,j,k,p,t,oo,ma;
memset(dp,-INF,sizeof(dp));
oo=dp[0][0];
dp[0][0]=0;
for(k=1; k<=n; k++)
{
for(i=500; i>=0; i--)
{
for(j=500; j>=0; j--)
{
ma=-INF;
for(p=0; p<v[k].size(); p++)
{
if(i>=v[k][p].x&&j>=v[k][p].y)
ma=max(ma,dp[i-v[k][p].x][j-v[k][p].y]+v[k][p].z);
}
dp[i][j]=max(dp[i][j],ma);
}
}
}
ans=0;
for(i=0;i<=500;i++)
{
for(j=0;j<=500;j++)
{
if(dp[i][j]<0) continue ;
ans=max(ans,i*d[1]+j*d[2]+dp[i][j]*d[3]);
t=INF;
if(c[1]>0) t=min(t,i/c[1]);
if(c[2]>0) t=min(t,j/c[2]);
if(c[3]>0) t=min(t,dp[i][j]/c[3]);
ans=max(ans,(i-t*c[1])*d[1]+(j-t*c[2])*d[2]+(dp[i][j]-t*c[3])*d[3]+t*dd);
}
}
}
int main()
{
int i,j,k,p,t,u,vv,test=0;
while(scanf("%d",&n),n)
{
for(i=1; i<=3; i++)
{
scanf("%d%d%d",&w[i],&s[i],&d[i]);
}
scanf("%d%d%d%d",&c[1],&c[2],&c[3],&dd);
for(i=1; i<=n; i++)
{
scanf("%d%d",&u,&vv);
v[i].clear();
for(j=0; j*w[1]<=u&&j*s[1]<=vv; j++)
{
for(k=0; k*w[2]<=u-j*w[1]&&k*s[2]<=vv-j*s[1]; k++)
{
for(p=0; p*w[3]<=u-j*w[1]-k*w[2]&&p*s[3]<=vv-j*s[1]-k*s[2]; p++)
{
if(j==0&&k==0&&p==0) continue ;
cur.x=j,cur.y=k,cur.z=p;
v[i].push_back(cur);
}
}
}
}
if(test) printf("\n");
solve();
printf("Case %d: %d\n",++test,ans);
}
return 0;
}