You are given an array of length . You can select distinct indexes and double the element in them.
The beauty of the array is the sum of any subarray of length . Find the maximum beauty over all permutations of array .
Input Format:
Output Format:
For each test case, print the maximum beauty over all permutations of .
Constraints:
First test case:
We can select indexes , , and (1-based indexing).
becomes . The permutation that gives maximum beauty is . Hence, the answer is .
Second test case:
We can select index (1-based indexing).
becomes . The permutation that gives maximum beauty is . Hence, the answer is .