5.4 ðŸ”„ âž• Rotate and Sum âž• ðŸŒ€

Score: 20pts

Time Limit: 5.00 sec

You are given an array of integers A of length n. Your task is to rotate the array to the right k times and return the maximum possible sum of the array at each step of rotation.Formally, if the initial array is represented as A[0], A[1], A[2], ..., A[n-1], after one right rotation, the array will be A[n-1], A[0], A[1], ..., A[n-2].Let the sum of the array S_i at each step i be the sum of all elements multiplied by their current index. So, the sum S_i for the i-th rotation is: [ S_i = 0 \times A_i + 1 \times A_{i+1} + 2 \times A_{i+2} + ... + (n-1) \times A_{n-1} ] Find the maximum possible value of S_i after rotating the array k times.

Constraints

1 â‰¤ n â‰¤ 10^5

1 â‰¤ k â‰¤ 10^9

-10^9 â‰¤ A[i] â‰¤ 10^9

1 â‰¤ k â‰¤ 10^9

-10^9 â‰¤ A[i] â‰¤ 10^9

Input Format

First line: an integer n (the size of the array) and k (the number of rotations).Second line: n space-separated integers representing the array A.

Output Format

A single integer: the maximum sum after k rotations.

Example 1

Input:

5 3

1 2 3 4 5

Output:

40

Explanation:

The initial sum S0 for the array [1, 2, 3, 4, 5] is: [ S_0 = 0 \times 1 + 1 \times 2 + 2 \times 3 + 3 \times 4 + 4 \times 5 = 40 ] Rotating once yields the array [5, 1, 2, 3, 4], and the sum S1 is: [ S_1 = 0 \times 5 + 1 \times 1 + 2 \times 2 + 3 \times 3 + 4 \times 4 = 34 ] Rotating again yields the array [4, 5, 1, 2, 3], and the sum S2 is: [ S_2 = 0 \times 4 + 1 \times 5 + 2 \times 1 + 3 \times 2 + 4 \times 3 = 33 ] After k=3 rotations, the maximum sum is still 40, so the output is 40.

5 3

1 2 3 4 5

Output:

40

Explanation:

The initial sum S0 for the array [1, 2, 3, 4, 5] is: [ S_0 = 0 \times 1 + 1 \times 2 + 2 \times 3 + 3 \times 4 + 4 \times 5 = 40 ] Rotating once yields the array [5, 1, 2, 3, 4], and the sum S1 is: [ S_1 = 0 \times 5 + 1 \times 1 + 2 \times 2 + 3 \times 3 + 4 \times 4 = 34 ] Rotating again yields the array [4, 5, 1, 2, 3], and the sum S2 is: [ S_2 = 0 \times 4 + 1 \times 5 + 2 \times 1 + 3 \times 2 + 4 \times 3 = 33 ] After k=3 rotations, the maximum sum is still 40, so the output is 40.