http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=4811 

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

思路：正常用完全背包会T，所以先用贪心预处理一下，找一个范围，先用性价比最高的填满，剩下的再用完全背包就ok了。

#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iostream>
#include