P11309 Dancing Cherry Blossom Rain

In memoriam tempus scholae - In those halcyon days of high school chemistry, we conducted an ethereal experiment where cobalt chloride met sodium hydroxide, creating a precipitate that descended like a magnificent storm of cherry blossoms from the heavens. Little $ \zeta $ asked her, “Have you ever witnessed the cherry blossoms?” She lifted her gaze, and in her obsidian pupils danced fragments of light, like stars caught in midnight pools. After a thoughtful pause, her eyes fixed upon me, a gentle smile gracing her lips. “I know your heart is set on Wuhan University,” she said. “That’s where I shall be too.” “This September... would you join me in watching the cherry blossoms?”

Little $ \zeta $ adores watching cherry blossoms. During the falling of $ n $ cherry blossoms, the beauty value of the $ i $-th falling blossom is $ a_i $. After each blossom falls, the total viewing score increases by the maximum beauty value among all fallen blossoms (including the current one and all previous ones). You can swap the falling order of two blossoms exactly k times (you cannot swap a blossom with itself, but you can swap the same pair multiple times). Your task is to maximize the total viewing score. Formally, given an array $ a $ of length $ n $, perform **exactly** $ k $ swaps to maximize $ \sum_{i=1}^n\max_{j=1}^ia_j $.

N/A

N/A

**「Sample 1 Explanation」** For the second test case, you can swap 10 and 11, making the total viewing score 11 + 11 = 22. **「Data Constraints」** For 100% of test cases: $ 1 \le T \le 500 $，$ 2 \le n \le 10^5 $，$ 0 \le k \le 10^9 $，$ \sum n \le 10^6 $，$ 1 \le a_i \le 10^9 $。 | Test Point ID | $ n $ | $ k $ | |:-:|:-:|:-:| | $ 1 $ | $ \le 50 $ | $ =0 $ | | $ 2 $ | - | $ =0 $ | | $ 3 \sim 4 $ | $ \le 50 $ | $ =1 $ | | $ 5 \sim 7 $ | - | $ =1 $ | | $ 8 \sim 10 $ | - | - |