CF2085D Serval and Kaitenzushi Buffet

Serval has just found a Kaitenzushi buffet restaurant. Kaitenzushi means that there is a conveyor belt in the restaurant, delivering plates of sushi in front of the customer, Serval. In this restaurant, each plate contains exactly $ k $ pieces of sushi and the $ i $ -th plate has a deliciousness $ d_i $ . Serval will have a meal in this restaurant for $ n $ minutes, and within the $ n $ minutes, he must eat up all the pieces of sushi he took from the belt. Denote the counter for uneaten taken pieces of sushi as $ r $ . Initially, $ r=0 $ . In the $ i $ -th minute ( $ 1\leq i\leq n $ ), only the $ i $ -th plate of sushi will be delivered in front of Serval, and he can do one of the following: - Take the $ i $ -th plate of sushi (whose deliciousness is $ d_i $ ) from the belt, and $ r $ will be increased by $ k $ ; - Eat one uneaten piece of sushi that he took from the belt before, and $ r $ will be decreased by $ 1 $ . Note that you can do this only if $ r>0 $ ; - Or, do nothing, and $ r $ will remain unchanged. Note that after the $ n $ minutes, the value of $ r $ must be $ 0 $ . Serval wants to maximize the sum of the deliciousnesses of all the plates he took. Help him find it out!

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ k $ ( $ 1\leq k

For each test case, print a single integer — the maximum possible sum of the deliciousnesses of all the plates Serval took.

In the first test case, it can be shown that Serval can eat up at most one plate of sushi. Since the second plate of sushi has the greatest deliciousness $ 6 $ among all the plates, he will take it from the belt in the second minute, and then eat it up in the following $ 2 $ minutes. Minute $ 1 $ $ 2 $ $ 3 $ $ 4 $ $ 5 $ Action — TakeEatEat — $ r $ after action $ 0 $ $ 2 $ $ 1 $ $ 0 $ $ 0 $ Deliciousnesses gained $ 0 $ $ 6 $ $ 6 $ $ 6 $ $ 6 $ In the second test case, it can be shown that it is optimal for Serval to eat up the first, third, and sixth plates of sushi. The sum of the deliciousnesses of these plates is $ 3 + 4 + 9 = 16 $ . Minute $ 1 $ $ 2 $ $ 3 $ $ 4 $ $ 5 $ $ 6 $ $ 7 $ ActionTakeEatTakeEat — TakeEat $ r $ after action $ 1 $ $ 0 $ $ 1 $ $ 0 $ $ 0 $ $ 1 $ $ 0 $ Deliciousnesses gained $ 3 $ $ 3 $ $ 7 $ $ 7 $ $ 7 $ $ 16 $ $ 16 $