Background

Farmer John has welcomed a new cow, Bessie. Each cow has a certain happiness value, and Farmer John hopes that Bessie can live a happier life here.

Problem Description

There are originally $n$ cows in the barn, with a happiness influence distance of $m$. Let $a_i$ denote the happiness value of the $i(1\le i\le n)$-th cow in the original barn. Bessie also has a happiness value $A$.

The total happiness of the whole barn is defined as $\sum\limits_{i=1}^{n-m+1}\ \max\limits_{i\le j\le i+m-1}\ a_j$. Bessie can be placed between any two cows, or at the beginning or the end. Farmer John wants to know: after Bessie comes here, what is the maximum possible total happiness of the whole barn.

Input Format

The first line contains three integers $n,m,A$, representing the number of cows, the happiness influence distance, and Bessie's happiness value.

The next line contains $n$ numbers $a_i$, representing the happiness value of the $i(1\le i\le n)$-th cow in the original barn.

Output Format

Output a single line representing the maximum total happiness of the whole barn after Bessie comes here.

3 2 50
60 100 70

270

Hint

[Sample Explanation]

• When Bessie is in the first position ($50,60,100,70$), the maximum total happiness of the whole barn is $\newcommand{\cases}[1]{\{#1\}}\max\cases{60,50}+\max\cases{60,100}+\max\cases{100,70}$, i.e., $60+100+100=260$.
• When Bessie is in the second position ($60,50,100,70$), the maximum total happiness of the whole barn is $\newcommand{\cases}[1]{\{#1\}}\max\cases{60,50}+\max\cases{50,100}+\max\cases{100,70}$, i.e., $60+100+100=260$.
• When Bessie is in the third position ($60,100,50,70$), the maximum total happiness of the whole barn is $\newcommand{\cases}[1]{\{#1\}}\max\cases{60,100}+\max\cases{100,50}+\max\cases{50,70}$, i.e., $100+100+70=270$.
• When Bessie is in the fourth position ($60,100,70,50$), the maximum total happiness of the whole barn is $\newcommand{\cases}[1]{\{#1\}}\max\cases{60,100}+\max\cases{100,70}+\max\cases{70,50}$, i.e., $70+100+100=270$.

Clearly, the maximum total happiness of the whole barn is $\newcommand{\cases}[1]{\{#1\}}\max\cases{260,260,270,270}=270$.

[Constraints and Notes]

For $100\%$ of the testdata, $1\le m\le n$, and $0\le a_i, A\le100$.

Translated by ChatGPT 5