题目描述

爱丽丝与鲍伯经常一起玩博弈游戏，理所当然地日久生情了。结婚以后他们生了很多孩子，理所当然地要给他们做衣服。由于他俩年轻时只是在玩游戏，理所当然地他们没多少钱。

现在知道他们一共要做N件衣服。而他们只会做M种衣服，每种衣服需要ai块布料和bi根线。又知道他们已经有C块布料和D根线，每块布料的价钱是Vc，每根线的价钱是Vd，请问他们最少额外花多少钱才能做成N件衣服？

输入要求

第一行一个整数T(T<50)，表示有几组数据。
每组数据第一行包含6个整数N,M,C,D,Vc,Vd。
接下来有M行，每行有两个数字ai,bi。
字母含义如上所述( 0 < N,M,ai,bi,Vc,Vd < = 50，0 < = C, D < = 2500 )。
(对于95%的数据，N,M,ai,bi,Vc,Vd的值不会超过20)

输出要求

对应每组数据输出例子序号以及最少花的钱数，具体格式见Sample Output。

输入样例

5

1 1 0 0 1 1
2 3

1 1 100 100 1 1
2 3

2 2 0 0 1 1
1 2
2 1

2 2 3 3 1 1
1 2
2 1

50 6 2000 2000 47 49
45 50
46 49
47 48
48 47
49 46
50 45

输出样例

Case 1: 5
Case 2: 0
Case 3: 6
Case 4: 0
Case 5: 35750

提示

来源

The 9th NBU Programming Contest