Max Element After Shifts

You are given a sequence of non-negative integers and an integer \(k\) representing the number of shift operations available. In one shift operation, you can choose a pair of consecutive elements and add the left element's value to the right element. Your task is to determine the maximum possible value of any element in the sequence after performing exactly \(k\) shift operations.

Mathematically, if the initial sequence is \(a_1, a_2, \ldots, a_n\) and the total sum of the elements is \(S = \sum_{i=1}^{n} a_i\), then one can show that the largest achievable value after \(k\) operations is \(S + k\).

Note: Even though the operations affect adjacent elements, the optimal strategy always accrues the total sum and then adds \(k\) to it.

inputFormat

The input is given from standard input (stdin) and consists of two lines:

• The first line contains two integers \(n\) and \(k\), where \(n\) is the length of the sequence and \(k\) is the number of shift operations.
• The second line contains \(n\) non-negative integers representing the elements of the sequence.

outputFormat

Output a single integer to standard output (stdout), which is the maximum possible value of any element in the sequence after performing \(k\) shift operations.

5 3
1 2 3 4 5

18