#OJ1318. 果

果

果

Time Limit: 2 Sec  Memory Limit: 128 MB

Description

    一天问题哥在外出游玩时发现了一个果园,果园里有好多苹果树,树上结满了苹果。问题哥从没有见过这么多苹果,苹果一共有三种,每种苹果有一个体积w和一个售价p,问题哥想用背包带走若干苹果并想卖最多的钱,而问题哥身上只有一个包并且包的体积是V(所摘的苹果的全部体积不能超过V,每种苹果的数量可以看成无数个),问题哥听说你是个优秀的程序猿Orz。。于是请你来帮忙写个程序判断一下带回去的苹果最多可以卖多少钱。

Input

    第一行输入一个数T(T <= 50)代表测试数据的组数。     每组测试数据一共有四行,前三行每行有两个数w和p (1 <= w <= 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

HINT

Append Code

Source