B. Array Recoloringtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an integer array $$$a$$$ of size $$$n$$$. Initially, all elements of the array are colored red.You have to choose exactly $$$k$$$ elements of the array and paint them blue. Then, while there is at least one red element, you have to select any red element with a blue neighbor and make it blue.The cost of painting the array is defined as the sum of the first $$$k$$$ chosen elements and the last painted element. Your task is to calculate the maximum possible cost of painting for the given array. InputThe first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases.The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 5000$$$; $$$1 \le k < n$$$).The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).Additional constraint on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$5000$$$.OutputFor each test case, print a single integer — the maximum possible cost of painting for the given array. ExampleInput33 11 2 35 24 2 3 1 34 32 2 2 2Output5 10 8 NoteIn the first example, you can initially color the $$$2$$$-nd element, and then color the elements in the order $$$1, 3$$$. Then the cost of painting is equal to $$$2+3=5$$$.In the second example, you can initially color the elements $$$1$$$ and $$$5$$$, and then color the elements in the order $$$2, 4, 3$$$. Then the cost of painting is equal to $$$4+3+3=10$$$.In the third example, you can initially color the elements $$$2, 3, 4$$$, and then color the $$$1$$$-st element. Then the cost of painting is equal to $$$2+2+2+2=8$$$.