You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ABC263D] Left Right Operation

题面翻译

有一个长度为 N 的数列 A={$a_1$,$a_2$,$a_3$...$a_n$}.

• 选择一个整数 X (0 $\le$X$\le$N) , 如果 X 选0，则不做任何操作，否则用 L 替换 $a_1$,$a_2$,$a_3$...$a_X$.
• 选择一个整数 Y (0 $\le$Y$\le$N) ，如果 Y 选0，则不做任何操作，否则用R替换 $a_N$,$a_{N-1}$,$a_{N-2}$...$a_{N-Y+1}$ .

求操作后 A 数列总和的最小值。

题目描述

長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。

あなたは以下の連続する操作をちょうど一度だけ行います。

• 整数 $x\ (0\leq\ x\ \leq\ N)$ を選ぶ。$x$ として $0$ を選んだ場合何もしない。 $x$ として $1$ 以上の整数を選んだ場合、$A_1,A_2,\ldots,A_x$ をそれぞれ $L$ で置き換える。
• 整数 $y\ (0\leq\ y\ \leq\ N)$ を選ぶ。$y$ として $0$ を選んだ場合何もしない。 $y$ として $1$ 以上の整数を選んだ場合、$A_{N},A_{N-1},\ldots,A_{N-y+1}$ をそれぞれ $R$ で置き換える。

操作後の $A$ の要素の総和として考えられる最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $L$ $R$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

答えを出力せよ。

样例 #1

样例输入 #1

5 4 3
5 5 0 6 3

样例输出 #1

14

样例 #2

样例输入 #2

4 10 10
1 2 3 4

样例输出 #2

10

样例 #3

样例输入 #3

10 -5 -3
9 -6 10 -1 2 10 -1 7 -15 5

样例输出 #3

-58

提示

制約

• $1\ \leq\ N\ \leq\ 2\times\ 10^5$
• $-10^9\ \leq\ L,\ R\leq\ 10^9$
• $-10^9\ \leq\ A_i\leq\ 10^9$
• 入力は全て整数

Sample Explanation 1

$x=2,y=2$ として操作をすると、数列 $A\ =\ (4,4,0,3,3)$ となり、要素の総和は $14$ になります。 これが達成可能な最小値です。

Sample Explanation 2

$x=0,y=0$ として操作をすると、数列 $A\ =\ (1,2,3,4)$ となり、要素の総和は $10$ になります。 これが達成可能な最小値です。

Sample Explanation 3

$L,R,A_i$ は負であることがあります。