---{"category_name":"easy","problem_code":"CLEARARR","problem_name":"Clear the Array","problemComponents":{"constraints":"- $1 \\leq T \\leq 200$\n- $1 \\leq N \\leq 5000$\n- $0 \\leq K \\leq \\lfloor \\frac{N}{2} \\rfloor$\n- $1 \\leq X \\leq 10^9$\n- $1 \\leq A_i \\leq 10^9$","constraintsState":true,"subtasks":"- 30 points : $1 \\leq R \\leq 10000$\n- 70 points : $1 \\leq R \\leq 10^9$\n","subtasksState":false,"inputFormat":"- The first line of the input contains $T$ - the number of test cases. Then the test cases follow.\n\n- Each test case contains 2 lines of input.\n\n- The first line of each test case contains three integers: $N$, $K$, and $X$ separated by spaces.\n\n- The second line of each test case contains $N$ space-separated positive integers, $A_1,A_2,\\ldots A_N$.\n","inputFormatState":true,"outputFormat":"For each test case, output on one line the minimum cost to clear the array.\n","outputFormatState":true,"sampleTestCases":{"0":{"id":1,"input":"3\n5 2 7\n9 10 11 12 13\n5 0 7\n9 9 9 9 9\n5 2 7\n9 1 2 3 10\n","output":"23\n45\n13\n","explanation":"For the first test case, we can remove $A_1$ for cost $9$, which makes the array $[10, 11, 12, 13]$. Then we can do the third operation to remove $10$ and $13$ for cost $7$, which makes the array $[11, 12]$. We can again do the third operation to remove $11$ and $12$ for cost $7$ which clears the array.\n\nThe total cost is therefore $23$, which is the minimum cost possible.","isDeleted":false}}},"video_editorial_url":"https://youtu.be/uLXX2etF-NM","languages_supported":{"0":"CPP14","1":"C","2":"JAVA","3":"PYTH 3.6","4":"CPP17","5":"PYTH","6":"PYP3","7":"CS2","8":"ADA","9":"PYPY","10":"TEXT","11":"PAS fpc","12":"NODEJS","13":"RUBY","14":"PHP","15":"GO","16":"HASK","17":"TCL","18":"PERL","19":"SCALA","20":"LUA","21":"kotlin","22":"BASH","23":"JS","24":"LISP sbcl","25":"rust","26":"PAS gpc","27":"BF","28":"CLOJ","29":"R","30":"D","31":"CAML","32":"FORT","33":"ASM","34":"swift","35":"FS","36":"WSPC","37":"LISP clisp","38":"SQL","39":"SCM guile","40":"PERL6","41":"ERL","42":"CLPS","43":"ICK","44":"NICE","45":"PRLG","46":"ICON","47":"COB","48":"SCM chicken","49":"PIKE","50":"SCM qobi","51":"ST","52":"SQLQ","53":"NEM"},"max_timelimit":1,"source_sizelimit":50000,"problem_author":"vishesh_s","problem_tester":"","date_added":"18-08-2021","tags":{"0":"cook132","1":"cook132","2":"easy","3":"easy","4":"greedy","5":"greedy","6":"sorting","7":"sorting","8":"vishesh_s"},"problem_difficulty_level":"Easy","best_tag":"","editorial_url":"https://discuss.codechef.com/problems/CLEARARR","time":{"view_start_date":1629658802,"submit_start_date":1629658802,"visible_start_date":1629658802,"end_date":1735669800},"is_direct_submittable":false,"problemDiscussURL":"https://discuss.codechef.com/search?q=CLEARARR","is_proctored":false,"visitedContests":{},"layout":"problem"}---### Read problems statements in [Mandarin Chinese](https://www.codechef.com/download/translated/COOK132/mandarin/CLEARARR.pdf), [Russian](https://www.codechef.com/download/translated/COOK132/russian/CLEARARR.pdf), and [Bengali](https://www.codechef.com/download/translated/COOK132/bengali/CLEARARR.pdf) as well.You are given an array $A$ of $N$ elements. You can do the following operations on that array:- Remove the leftmost element of the array, with index $l$, for the cost $A_l$. This can be done any number of times if the array is non-empty (has at least $1$ element).- Remove the rightmost element of the array, with index $r$, for the cost $A_r$. This can be done any number of times if the array is non-empty (has at least $1$ element).- Remove both the leftmost and rightmost element, with indexes $l$ and $r$ respectively, for a fixed cost $X$ which is given. This operation can only be done $K$ times and only if the array has at least $2$ elements left.If the array has only $1$ element left, then the rightmost element is the same as the leftmost element so the first and second operations will have the same cost.You have to print the minimum cost to *clear the array* (remove all elements using one of the three operations above).**NOTE: The answer may not fit in 32-bit integers, so please use 64-bit data types in your programming language.**<aside style='background: #f8f8f8;padding: 10px 15px;'><div>All submissions for this problem are available.</div></aside>