There are many great athletes in the world, and it's very hard to say who is the best in the world at a particular sport, especially when different athletes have won different competitions. Here's one possible system for ranking athletes:

1. Determine the number **P** of finishing places in any competition that will be worth points for athletes, and how many points **S _{i}** each of those finishing places is worth. For example, for

2. Since not all competitions are equally important, assign a weight **W _{i}** to each one. The score gained by an athlete for a competition will be the points from step 1, modified by the weight for that competition. For example, we may decide that Olympics has a weight of 5, and, continuing with our example from above, the winner of the Olympics would receive 5 * 1000 = 5000 points.

3. Since we don't want to reward athletes simply for participating in many competitions, we count only the **M** highest scores received by an athlete across all competitions. For example, if **M** = 2 and an athlete earns scores of 1000*5, 500*1, and 300*3 in three different competitions, only the 5000 and 900 would be counted.

You are given the points per finishing place, the weights of the competitions, and the results of the competitions. Can you rank all of the athletes who appeared in the competitions? If multiple athletes have the same score, they will share the same rank and listed in alphabetical order of their names.

The first line of the input gives the number of test cases, **T**. **T** test cases follow; each test case consists of the following:

1. One line with an integer **P**, the number of top places for which points are awarded.

2. One line consists with **P** integers representing the scores **S _{i}** for the top places, starting with first place and continuing down the places.

3. One line with an integer

5. One line with an integer

For each test case, output one line containing "Case #x:", where x is the test case number (starting from 1). Then output one line for each athlete, from highest rank to lowest rank, with the format `r: name`

, where `r`

is the rank of the athlete and `name`

is the name of the athlete. You need to rank all of the athletes that appeared in the input.

Time limit: 30 seconds per test set.

Memory limit: 1 GB.

1 ≤ **T** ≤ 10.

1 ≤ **S _{i}** ≤ 1000.

1 ≤

Each name consists only of characters

`A`

through `Z`

, and is at most 10 characters long.
1 ≤ **P** ≤ 10.

1 ≤ **N** ≤ 10.

1 ≤ **M** ≤ 10.

1 ≤ **P** ≤ 100.

1 ≤ **N** ≤ 100.

1 ≤ **M** ≤ 100.

Sample Input

1 2 1000 500 6 5 BOLT GAY 4 GAY BOLT 1 GAY TIANBING 1 GAY PEIMENG 1 TIANBING LARRY 1 PEIMENG LARRY 2

Sample Output

Case #1: 1: BOLT 2: GAY 3: PEIMENG 3: TIANBING 5: LARRY

Alien tech company G has a very old file transfer tool that is still in use today. While the tool is running, it reassures users by giving status updates on both the percentage of files transferred so far and the number of files transferred so far. The status updates during the process might look like this:

20% |==>-------| 1 files transferred 100% |==========| 5 files transferred

But the percentage isn't precise; it is simply truncated before the decimal point (i.e. floored to the next lowest or equal 1%). That is, both 1.2% and 1.7% would be displayed as 1%.

Some users may want to know the exact total number of files, so you want to modify the tool so that the status updates look like this:

20% |==>-------| 1 out of5files transferred 100% |==========| 5 out of5files transferred

But you've realized that it may or may not be possible to know the number of files. Given the status updates that the tool displays, either figure out how many files there are, or determine that it can't be done (i.e., there are multiple possible values for the number of files). The status updates are not guaranteed to occur at regular intervals and are not guaranteed to occur whenever a file is transferred.

The first line contains **T**, the number of test cases. **T** test cases follow. Each test case consists of one line with an integer **N**, the number of status updates output by the tool, followed by **N** lines with the format P_{i} K_{i}, where P_{i} and K_{i} are integers representing the percentage and number of files transferred at some point in the process. The updates are given listed in chronological order -- that is, both the P_{i} values and the K_{i} values are nondecreasing throughout a test case.

For each case, output a line starts with "Case #x: y", where x is the number of the case (starting from 1), and y is either the total number of files, or `-1`

if that number is ambiguous.

Time limit: 30 seconds per test set.

Memory limit: 1 GB.

1 ≤ **T** ≤ 50.

1 ≤ **N** ≤ 100.

0 ≤ P_{i} ≤ 100

0 ≤ K_{i} ≤ 2000

The answer is guaranteed not to exceed 2000.

0 ≤ K_{i} ≤ 10^{15}

The answer is guaranteed not to exceed 10^{15}.

Sample Input

3 2 20 1 100 5 10 25 241 27 262 43 407 44 413 57 536 64 601 67 637 84 789 95 893 96 903 10 0 0 8 2 8 2 17 4 30 7 39 9 69 16 73 17 82 19 91 21

Sample Output

Case #1: 5 Case #2: -1 Case #3: 23

The country of elves is planning to hold an elimination tournament, and there are 2^{N} elves who would like to take part. At the start of the tournament, they will be given unique ID numbers from 1 to 2^{N}, and the Elf President will line them up in some order.

The tournament is a series of matches between two elves, and every match has one winner and one loser (there are no ties). In the first round, the first elf in the line competes against the second elf in the line, the third elf competes against the fourth elf, and so on. After the first round, the 2^{N-1} elves who lost leave the line, and the 2^{N-1} elves who won remain where they are. Then, the remaining elves play the second round in the same way: the first remaining elf in the line competes against the second remaining elf in the line, the third remaining elf competes against the fourth remaining elf, and so on. After **N** rounds, there will be only one elf remaining, and that elf is the winner.

**M** of the elves are sensitive, which means that they will be very sad if they have to compete in matches against their friends during the games. Specifically, the ith elf will be sad if they have to compete with their friends in the first **K _{i}** rounds. (Note that friendship is not necessarily mutual: if one elf considers another elf to be a friend, the other elf does not necessarily consider that elf to be a friend.)

The Elf President wants to know: is there a way to specify the initial positions of all 2^{N} elves to guarantee that no elf will be sad, no matter what happens in the tournament?

The first line of the input gives the number of test cases, **T**. **T** test cases follow. Each test case consists of one line with two integers **N** and **M**, then **M** sets of two lines each, in which the first line has integers **E _{i}**,

For each test case, output one line containing "Case #x: ", where x is the case number (starting from 1), followed by `YES`

or `NO`

.

Time limit: 30 seconds per test set.

Memory limit: 1 GB.

1 ≤ **T** ≤ 200.

0 ≤ **M** ≤ 2^{N}.

1 ≤ **E _{i}** ≤ 2

1 ≤

1 ≤ **N** ≤ 3.

**N** = 4.

Sample Input

3 1 1 1 1 1 2 2 2 1 1 1 2 3 1 1 4 3 3 1 2 2 3 4 2 2 2 5 6 7 1 1 8

Sample Output

Case #1: NO Case #2: YES Case #3: YES

You have a square **N** by **N** matrix M of nonnegative integers. We would like to make a list of the maximum values in every sub-matrix of size **K** by **K** within M, and then find the sum of those values together. (Note that the same entry of M might be the maximum value in more than one sub-matrix, in which case it will show up multiple times in the list.) Can you find that sum?

To simplify the input of the matrix, you are given two arrays **A** and **B** of length **N**, and two integers **C** and **X**. Then the entry M_{ij} (for the ith row and jth column of the matrix) equals (**A _{i}***i+

The first line of the input gives the number of test cases, **T**. **T** test cases follow. Each test case begins with one line with four integers, **N**, **K**, **C** and **X**. Then there are two lines with **N** integers each, representing the arrays **A** and **B**.

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 sum of the maximum values in all sub-matrices of size **K** by **K**.

Memory limit: 1 GB.

1 ≤ **T** ≤ 100.

1 ≤ **A _{i}**,

1 ≤

1 ≤

1 ≤

Time limit: 30 seconds.

1 ≤ **N** ≤ 50.

Time limit: 90 seconds.

1 ≤ **N** ≤ 3000.

Sample Input

3 1 1 1 5 1 1 2 1 5 11 1 2 3 4 3 2 3 109 6 4 3 2 1 5

Sample Output

Case #1: 3 Case #2: 19 Case #3: 80

`3`

So the sum of maximum values is 3.

In the second test case, the matrix is:

`9 3`

`1 6`

So the sum of maximum values is 19.

In the third test case, the matrix is:

`11 11 24`

`13 13 26`

`14 14 27`

Test Data

We recommend that you practice debugging solutions without looking at the test data.

Test Data

We recommend that you practice debugging solutions without looking at the test data.

Uses DFS to generate one of the possible orders.
Some optimizations for large datasets:
1. Pre-process: checks whether there will be one elf who have at least 2^n-2^(n-i) friends and don't want to meet its friends at the first (n-i) matches.
2. Pre-process: checks whether there are 3 different elves who don't want to meet each other at the first n - 1 matches. (n >= 1)
3. Pre-process: checks whether there are 5 different elves who don't want to meet each other at the first n - 2 matches. (n >= 2)
4. Changes the order of searching by arranging the elves who have more restrictions on their friends at first.

Test Data

We recommend that you practice debugging solutions without looking at the test data.

Test Data

We recommend that you practice debugging solutions without looking at the test data.