BDOI16D - One Punch Man

no tags 

One Punch Man

Saitama is the most powerful hero alive. Having apparently trained himself to superhuman conditions, Saitama faces a self-imposed existential crisis, as he is now too powerful to gain any thrill from his heroic deeds. Every monster he faces, is killed with only one of his punch.

 

There are N groups of monsters on a line , ith of them is positioned at distance Xi from the beginning of that line and has Vi members. When Saitama punches the ground at P, all monsters within R vicinity of that punch ( meaning from P-R to P+R both inclusive ) are killed by the shockwave . Saitama is tired after all his hero duties. So he will punch atmost K times. Can you help him figure out , what is the maximum number of monsters he can kill.

 

Input:

The first line contains number of test case T. Then T testcases follow. First line of each test case contains three integers N,R and k. Following N lines contains two space separated intergers Xi and Vi .

 

Limits:

T ≤ 10
1 ≤
N ≤ 105
1 ≤
Vi ≤ 104

1 ≤ K ≤ 50

 

For Easy Version:
0 ≤
R,Xi ≤ 104

 

For Hard Version:
0 ≤
R,Xi ≤ 108

 

 

Output:

For each test case, print a line "Case t: m" where t is the test case number and m is the the maximum number of monsters Saitama can kill.

Input

Output

2

4 3 1

6 10

12 110

19 100

24 30

5 3 2

3 3

5 2

3 8

10 5

0 5

Case 1: 130

Case 2: 23

 

 

 

Explanation of sample input:

In sample 1, Saitama can punch at position 21 or 22 to kill 130 monsters. If he punches at position 21 then the shockwave ranges from 18 to 24, killing monsters at 19 and 24. Similarly if he punches at 22 then then shockwave will kill from 19 to 25. Punch at no other position will kill more monsters.

 

In Sample 2 , Saitama can kill all monsters with 2 punches.



Problem Setter: Moinul Shaon

 


hide comments
xalen: 2016-11-26 11:11:03

how to avoid time limit exceed?


Added by:Rezwan
Date:2016-10-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Bangladesh Olympiad on Informatics 2016 National; Problem Setter: Moinul Shaon