← 返回题目列表

Codeforces · 354/A

A. 瓦夏和机器人

中文机器翻译题面 查看原题

Vasya 有 n 个物品排成一行。这些项目按从 1 到 n 的数字连续编号,最左边的项目编号为 1,最右边的项目编号为 n。每个物品都有一个重量,第 i 个物品的重量为 wi 公斤。

Vasya 需要收集所有这些物品,但他不会自己完成。他使用他的全新机器人。该机器人有两只不同的手臂——左一只和右一只。机器人可以连续执行以下动作:

1. 左手拿起最左边的物品,花费 wi · l 能量单位(wi 是最左边物品的重量,l 是某个参数)。如果前一个动作相同(左手),则机器人花费额外的 Ql 能量单位;
2.用右手拿起最右边的物品,花费wj · r个能量单位(wj是最右边物品的重量,r是某个参数)。如果前一个动作相同(右手),则机器人花费额外的 Qr 能量单位;

当然,Vasya 希望对机器人进行编程,使机器人消耗尽可能少的能量。他要求你解决这个问题。您的任务是找到机器人收集所有物品所需的最小能量单位数。

输入

第一行包含五个整数 n、l、r、Ql、Qr (1 ≤ n ≤ 105;1 ≤ l,r ≤ 100;1 ≤ Ql,Qr ≤ 104)。

第二行包含 n 个整数 w1, w2, ..., wn (1 ≤ wi ≤ 100)。

输出

在单行中打印一个数字——问题的答案。

示例

输入 #1

3 4 4 19 1
42 3 99

输出 #1

576

输入 #2

4 7 2 3 9
1 2 3 4

输出 #2

34

注意

考虑第一个样本。当 l = r 时,我们可以依次取出一项:首先从左侧取出,然后从右侧取出,最后从左侧取出。机器人总共消耗 4·42 + 4·99 + 4·3 = 576 能量单位。

第二个样本。最佳解决方案是从右侧取出一项,然后从左侧取出一项,再从右侧取出两项。机器人总共消耗 (2·4) + (7·1) + (2·3) + (2·2 + 9) = 34 个能量单位。