题目描述

一条通道被分成 $n$ 段，第 $i$ 段连接整数点 $i-1$ 和 $i$。每个整数点处的高度只能是 $1$ 或 $2$。设点 $i$ 的高度为 $h_i$（$0\le i\le n$）。

给定一个长度为 $n$ 的 01 串 $s$，以及三个正整数 $a,b,c$：

• 若 $s_i=1$，则第 $i$ 段必须满足 $h_{i-1}=h_i=2$，这一段的花费为 $a$。
• 若 $s_i=0$，则 $h_{i-1}$ 和 $h_i$ 可以各自取 $1$ 或 $2$。若 $h_{i-1}=h_i$，这一段花费 $a$；若 $h_{i-1}\ne h_i$，这一段是折线形通道，花费 $2a$。
• 在每个整数点 $i$（$0\le i\le n$）处需要焊接一次。若 $h_i=1$，焊接花费 $b$；若 $h_i=2$，焊接花费 $c$。

求满足条件的最小总花费。

输入格式

第一行四个整数 $n,a,b,c$，满足 $1\le n\le 2\times10^5$，$1\le a,b,c\le 10^9$。

第二行一个长度为 $n$ 的 01 字符串 $s$。

输出格式

输出一行一个整数，表示最小总花费。

8 2 5 10
00110010

94

3 1 2 3
000

11

样例解释

样例 $1$：一种最优方案为

第 $1$ 段高度不变，花费 $2$；第 $2$ 段从 $1$ 变到 $2$，花费 $4$；第 $3,4$ 段为必须建在高度 $2$ 的段，各花费 $2$；第 $5$ 段从 $2$ 变到 $1$，花费 $4$；第 $6$ 段从 $1$ 变到 $2$，花费 $4$；第 $7$ 段为必须建在高度 $2$ 的段，花费 $2$；第 $8$ 段从 $2$ 变到 $1$，花费 $4$。通道总花费 $24$。焊接点在高度 $1$ 的有 $0,1,5,8$ 四个，在高度 $2$ 的有 $2,3,4,6,7$ 五个，焊接费用 $4b+5c=20+50=70$。总花费 $24+70=94$。

样例 $2$：三段全为 $0$。全部建在高度 $1$ 时花费 $3a+4b=3+8=11$；全部建在高度 $2$ 时花费 $3a+4c=3+12=15$。最小值为 $11$。

数据范围与约定

下发样例

下发样例下载