2910 -- Downpayment

Language:

Downpayment

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 179		Accepted: 43

Description

Large houses cost a lot of money. Typically, a loan is required in order to finance the investment. The credit institutions provide a plentitude of different mortgage alternatives, e.g., you may choose to tie the current interest rate for a period. During this period, you may not change institution or terms. After this period, you may change terms, at a penalty cost, or start a new period. The tricky thing is that the interest changes over time.

In this problem, we make the absurd assumption that a crystal ball is at your disposal. That is, you know, in advance, what the different interest rates for all institutions are going to be. Given this information, your task is to come up with a plan for the payments which minimizes the absolute amount of money paid over the entire period.

For each month, the following items are added to the debt:

Any possible penalties for changing the terms. For the first month, you may choose any alternative without penalty.
The interest for the dept, including the penalty.

After these items has been added, the amount is rounded to two decimals towards zero. Then, a fixed amount is paid, i.e., the debt is reduced by this amount. However, if the debt is less than the fixed amount, only the remaining debt is paid and the loan is fully paid. You do not have to pay any penalty if the binding time for your current terms is not at end when the loan is paid.

Input

On the first line of input there is one integer, N ≤ 50, giving the number of test cases in the input. Each test case starts with a line containing one integer m and two floating point numbers x and y with at most two decimals, where 1 ≤ m ≤ 20 stands for the number of different loan alternatives, 1 ≤ x ≤ 1000000 stands for the investment amount, and 1 ≤ y ≤ 10000 is the fixed amount paid every month. Following this line are m lines, each with an integer l, which stands for the binding time in months of this alternative, 1 ≤ l ≤ 60. Following these lines are yet another m lines, each with m floating point numbers with at most two decimals, which gives C(a, b) ≥ 0, the cost of switching from loan alternative a to loan alternative b. Now, C(x, y) = C(y, x) and C(x, x) = 0. After these lines, a line with a single integer t follows. t stands for the number of months that interest information is known. You may assume that t is sufficiently large for the optimal solution. Ending the test case are t lines, each with m floating point numbers, giving the actual monthly interest rates, in percent, for all of the alternatives for each month. You may assume that the loan can be fully paid after 100 years. You may also assume that all lines of input are maximum 255 characters.

Output

Start each test case with a line stating the test case, as this: “Test case u”. For every month required to pay the loan, output one line stating which alternative would be the best one, as this: “Month v: Alternative w” (there should be only one space between “:” and “A”). u, v, w all start at 1. Ending the test case, output a line stating the total amount paid, with two decimal digits: “Total: s” (there should be only one space between “:” and s).

Sample Input

Sample Output

Test case 1
Month 1: Alternative 1
Month 2: Alternative 1
Month 3: Alternative 1
Total: 209.45
Test case 2
Month 1: Alternative 1
Month 2: Alternative 2
Month 3: Alternative 2
Month 4: Alternative 2
Total: 354.85

Source

Svenskt Mästerskap i Programmering/Norgesmesterskapet 2002