题目描述

注意：本题中的所有数列下标从 $0$ 开始。

小 R 是一个可爱的女孩子，她喜欢研究无穷数列。

她称一个无穷数列 $b$ 是美妙的，当且仅当存在自然数 $k_0$，使得对于所有 $k\ge k_0$，都满足 $b$ 中下标在区间 $[k_0,k]$ 内的所有数的和非负（即 $\sum_{i=k_0}^kb_i\ge 0$）。例如，数列 $\alpha_i=i-5$ 是美妙的，取 $k_0=5$ 符合要求；但 $\beta_i=-i$ 不是美妙的。

她目前只有一个长度为 $n$ 的有穷数列 $a$，可以进行任意次以下三种操作：

1. 花费 $p$ 的代价，选择一个整数 $i$（$0\le i < n$），将 $a_i$ 增加一。
2. 花费 $q$ 的代价，选择一个整数 $i$（$0\le i < n$），将 $a_i$ 删除，同时更新 $n$ 为新的数列长度。不能将数列删空。
3. 花费 $r$ 的代价，选择两个整数 $i,j$（$0\le i < j < n$），交换 $a_i$ 与 $a_j$。

她希望在若干次操作后，用无限个有穷数列 $a$ 依次相接得到无穷数列 $b$（即 $b_i=a_{i\bmod n}$），使得 $b$ 是美妙的。请你求出最小的代价。

输入格式

第一行四个整数 $n,p,q,r$。

第二行 $n$ 个整数，表示数列 $a$。

输出格式

一行，一个整数，表示最小代价。

5 1 2 5
2 -2 3 -3 -1

1

5 2 1 5
2 -2 3 -3 -1

1

5 1 1 1
0 1 2 3 4

0

提示

样例 $1$ 解释

花费 $p=1$ 的代价将 $a_3$ 增加一，得到数列 $b=[2,-2,3,-2,-1,2,-2,3,-2,-1,\cdots]$ 是美妙的，取 $k_0=2$ 符合要求。

可以证明不存在代价更小的方案。

样例 $2$ 解释

花费 $q=1$ 的代价将 $a_1$ 删除，得到数列 $b=[2,3,-3,-1,2,3,-3,-1,\cdots]$ 是美妙的，取 $k_0=0$ 符合要求。

可以证明不存在代价更小的方案。

数据范围

本题采用捆绑测试。只有通过子任务中所有测试点以及所有依赖的子任务，才能获得相应的分数。

对于全部数据：$1\le n\le 10^5$，$1\le p,q,r\le 10^9$，$|a_i|\le 10^9$。

• 子任务一（$10$ 分）：$n=1$。
• 子任务二（$10$ 分）：$n\le 10$。依赖子任务一。
• 子任务三（$20$ 分）：$|a_i|\le 1$。
• 子任务四（$20$ 分）：$\sum|a_i|\le 10^5$。依赖子任务三。
• 子任务五（$40$ 分）：无特殊限制。依赖子任务一、二、三、四。