P17682 [IO 2025 #2] 电车站

顿河畔罗斯托夫有一套独特的电车线路系统。每个车站用一个长度为 $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$。

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