题目描述

顿河畔罗斯托夫有一套独特的电车线路系统。每个车站用一个长度为 $n$ 的二进制字符串编码，其中每一位表示该站是否提供一种服务：$1$ 表示提供，$0$ 表示不提供。

若两个车站的编码恰好有一位不同，电车就可以在这两个车站之间行驶。也就是说，电车只能往返于这样的“相邻”车站。

每次到达一个车站时，需要支付该站所有服务的费用之和：如果其编码的第 $i$ 位是 $1$，就要支付第 $i$ 种服务的费用 $c_i$。起始车站不收费，之后每次到达车站均按上述规则收费。

请计算从起始车站 $s$ 到终点车站 $e$ 的最小总费用。

输入格式

第一行包含三个以空格分隔的值：服务数量 $n$、起点编码 $s$、终点编码 $e$。其中 $1\le n\le1000$，$s$ 和 $e$ 均为长度恰好为 $n$、只含字符 0 和 1 的字符串。

第二行包含 $n$ 个整数 $c_1,c_2,\ldots,c_n$，表示各项服务的费用，其中 $1\le c_i\le10^6$。

输出格式

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

3 101 011
1 2 3

8

5 00000 11111
5 4 3 2 1

35

4 1111 1000
200 20 20 20

320