write a go solution for 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<=t<=10^3) — the number of test cases.The first line of each test case contains two integers n and k (2<=n<=5000; 1<=k<n).The second line contains n integers a_1,a_2,...,a_n (1<=a_i<=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.. Output only the code with no comments, explanation, or additional text.