#216843. [GKS 2021 #F] Festival

You have just heard about a wonderful festival that will last for days, numbered from to . There will be attractions at the festival. The -th attraction has a happiness rating of and will be available from day until day , inclusive.

You plan to choose one of the days to attend the festival. On that day, you will choose up to attractions to ride. Your total happiness will be the sum of happiness ratings of the attractions you chose to ride.

What is the maximum total happiness you could achieve?

The first line of the input gives the number of test cases, . test cases follow.

The first line of each test case contains the three integers, , and . The next lines describe the attractions. The -th line contains , and .

For each test case, output one line containing Case #: , where is the test case number (starting from ) and is the maximum total happiness you could achieve.

样例输入 1

2
10 4 2
800 2 8
1500 6 9
200 4 7
400 3 5
5 3 3
400 1 3
500 5 5
300 2 3

样例输出 1

Case #1: 2300
Case #2: 700

In sample test case , the festival lasts days, there are attractions, and you can ride up to attractions.

If you choose to attend the festival on the th day, you could ride the first and second attractions for a total happiness of . Note that you cannot also ride the third attraction, since you may only ride up to attractions. This is the maximum total happiness you could achieve, so the answer is .

In sample test case , the festival lasts days, there are attractions, and you can ride up to attractions.

If you choose to attend the festival on the rd day, you could ride the first and third attractions for a total happiness of . This is the maximum total happiness you could achieve, so the answer is .

Limits

.

.

, for all .

, for all .

Test Set

.

.

Test Set

For at most test cases:

• .
• .

For the remaining cases, .