#216670. [GKS 2018 #D] Candies

Supervin loves to eat candies. Today, his favorite candy shop is offering candies, which are arranged in a line. The -th candy in the line (counting starting from 1) has a sweetness level . Note that the sweetness level of a candy might be negative, which means the candy tastes bitter.

Supervin likes to eat sweet candies. However, candies with a combined sweetness level of more than would be too much sweetness even for him. Supervin also realises that a candy with an odd sweetness level is "odd", and he does not want to eat more than odd candies. In other words, an odd candy is a candy with a sweetness level that is not evenly divisible by 2. Additionally, since Supervin is in a rush, he can only eat a single contiguous subset of candies.

Therefore, he wants to eat a contiguous non-empty subset of candies in which there are at most odd candies and the total sweetness level is maximized, but not more than . Help Supervin to determine the maximum total sweetness level he can get, or return IMPOSSIBLE if there is no contiguous subset satisfying these constraints.

The first line of the input gives the number of test cases, T. T test cases follow. Each test case contains two lines. The first line contains three integers , , and , as described above. The second line contains seven integers , , , , , , ; these values are used to generate the values , as follows:

We define:

• , for to .
• , for to .

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum total sweetness level Supervin can get, or IMPOSSIBLE if there is no possible contiguous subset satisfying the problem constraints.

样例输入 1

2
6 1 1000000000000000
1 1 1 1 0 100 0
6 1 -100
1 1 1 1 0 100 0

样例输出 1

Case #1: 13
Case #2: IMPOSSIBLE

样例输入 2

3
10 1 8
4 3 4 1 5 20 -10
10 2 8
4 3 4 1 5 20 -10
10 1 8
4 3 4 1 5 20 -19

样例输出 2

Case #1: 7
Case #2: 8
Case #3: -5

In Sample Case #1, the generated array of sweetness values is: [, , , , , ], where the bold and underlined numbers are the odd numbers. Since Supervin can only eat one odd candy, he can get a maximum total sweetness level by taking the fifth and the sixth candies.

In Sample Case #2, the generated array of sweetness values is the same as in Sample Case #1. However, this time Supervin cannot eat candies with a total sweetness level of more than , so no contiguous subset of candies satisfies the constraints.

Note: We do not recommend using interpreted/slower languages for the Large dataset of this problem.

Limits

.

.

.

.

.

.

Small dataset (Test set 1 - Visible)

.

Large dataset (Test set 2 - Hidden)

.