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

Festival solution kickstart

Problem

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

You plan to choose one of the days to attend the festival. On that day, you will choose up to KK 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?

Festival solution kickstart

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

The first line of each test case contains the three integers, DDNN and KK. The next NN lines describe the attractions. The ii-th line contains hihisisi and eiei.

Output

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

Festival solution kickstart

Memory limit: 1 GB.
1T1001≤T≤100.
1KN1≤K≤N.
1sieiD1≤si≤ei≤D, for all ii.
1hi3×1051≤hi≤3×105, for all ii.

Test Set 1

Time limit: 20 seconds.
1N10001≤N≤1000.
1D10001≤D≤1000.

Festival solution kickstart

Time limit: 90 seconds.
For at most 1010 test cases:

  • 1N3×1051≤N≤3×105.
  • 1D3×1051≤D≤3×105.

For the remaining cases, 1N,D10001≤N,D≤1000.

 

Sample

Sample Input
content_copy
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
Sample Output
content_copy
Case #1: 2300
Case #2: 700

In sample test case 1, the festival lasts D=10D=10 days, there are N=4N=4 attractions, and you can ride up to K=2K=2 attractions.

If you choose to attend the festival on the 6th day, you could ride the first and second attractions for a total happiness of 800+1500=2300800+1500=2300. Note that you cannot also ride the third attraction, since you may only ride up to K=2K=2 attractions. This is the maximum total happiness you could achieve, so the answer is 23002300.

In sample test case 2, the festival lasts D=5D=5 days, there are N=3N=3 attractions, and you can ride up to K=3K=3 attractions.

If you choose to attend the festival on the 3rd day, you could ride the first and third attractions for a total happiness of 400+300=700400+300=700. This is the maximum total happiness you could achieve, so the answer is 700700.

Leave a Comment