**注意：本题中的所有数列下标从 $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$ 增加一。
1. 花费 $q$ 的代价，选择一个整数 $i$（$0\le i < n$），将 $a_i$ 删除，同时更新 $n$ 为新的数列长度。**不能将数列删空。**
1. 花费 $r$ 的代价，选择两个整数 $i,j$（$0\le i < j < n$），交换 $a_i$ 与 $a_j$。
她希望在若干次操作后，用无限个有穷数列 $a$ 依次相接得到无穷数列 $b$（即 $b_i=a_{i\bmod n}$），使得 $b$ 是美妙的。请你求出最小的代价。
## Input
第一行四个整数 $n,p,q,r$。
第二行 $n$ 个整数，表示数列 $a$。
## Output
一行，一个整数，表示最小代价。
[samples]
## Note
**样例 $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$ 分）：无特殊限制。依赖子任务一、二、三、四。