Barn Happiness Maximization

There are originally \(n\) cows in the barn with happiness values \(a_1, a_2, \ldots, a_n\). A contiguous block of cows of length \(m\) contributes to the barn's total happiness by the maximum happiness in that block. Formally, the barn's total happiness without Bessie is defined as:

\[ S = \sum_{i=1}^{n-m+1} \max_{i \le j \le i+m-1} a_j \]

Bessie has a happiness value \(A\) and can be inserted at any position in the lineup (i.e. before the first cow, between any two cows, or after the last cow). After insertion, the new lineup has \(n+1\) cows and the barn's total happiness becomes:

\[ S' = \sum_{i=1}^{(n+1)-m+1} \max_{i \le j \le i+m-1} b_j, \]

where \(b\) is the new sequence after inserting \(A\) at an optimal position. Your task is to compute the maximum possible total happiness \(S'\) after Bessie is inserted optimally.

inputFormat

The first line contains three integers \(n\), \(m\), and \(A\) (\(1 \leq n, m \leq 10^5\), values may be adjusted according to hidden constraints). The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\), representing the happiness values of the original cows.

outputFormat

Output a single integer representing the maximum total barn happiness after inserting Bessie optimally.

sample

3 2 10
1 5 2

25