Description
以前，有个神秘的院子里面有三种苹果，每个苹果的数量是无限的。有一个小姑娘带了一个大袋子来到院子，她从来没见过这么多的苹果。每种苹果都有大小以及出售的价格，小姑娘想获得最大的利润，但是她不知道怎么才能做到。于是她来向你寻求帮助，你能告诉她能获得的最大价值吗？

Input
第一行一个整数T(T <= 50)，表示测试数据的组数。

每组测试数据有四行组成，前三行每行有两个整数S和P，分别表示每种苹果的大小(1 <= S <= 100)和价格(1 <= P <= 10000)

第四行有一个整数V(1 <= V <= 100,000,000)表示小姑娘袋子的大小。

Output
每组测试数据输出组数和小姑娘能得到的最大的价值。

Sample Input
1
1 1
2 1
3 1
6
Sample Output
Case 1: 6

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int N;
int k;
long long q;
long long dp[10002];
struct pple {int cou;int price;double onePrice;
};
pple f[3];
bool compare(pple a, pple b)
{return a.onePrice < b.onePrice;
}
void apple()
{sort(f, f + 3, compare);long long ans = 0;if (q > 900) {ans = ((q - 900) / f[2].cou) * f[2].price;q = 900 + (q - 900) % f[2].cou;}//cout<<"f2="<<f[2].cou<<" "<<f[2].price<<endl;//cout<<"q="<<q<<" "<<ans<<endl;for(int i=0;i<=q;i++) dp[i]=0;for (int i = 0; i < 3; i++) {for (int j = f[i].cou; j <= q; j++) {dp[j] = max(dp[j], dp[j - f[i].cou] + f[i].price);}}ans += dp[q];cout << "Case " << k << ": " << ans << endl;
}
int main()
{k = 0;cin >> N;while (N--) {k++;for (int i = 0; i < 3; i++) {cin >> f[i].cou;cin >> f[i].price;f[i].onePrice = 10.0 * f[i].price / f[i].cou;}cin >> q;apple();}
}