小䓤的一个数字

题号：NC222907
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一个长度为 $n$ 的序列 $\{a_i\}_{i=0}^{n-1}$ 和一个大数 $V$ 。

其中 $V$ 用一个长度为 $n$ 的 $0/1$ 串 $\{c_i\}_{i=0}^{n-1}$ 形式读入，其中 $c_i$ 表示 $V$ 二进制表示下从低到高的第 $i$ 位。

现在要使用任意次操作，将一个初始为 $0$ 的数 $S$ 变成 $V$ ,一次操作为下列两种之一：

- 将 $S$ 从低到高第 $i$ 位二进制位 $01$ 翻转，代价为 $a_i$ 。
- 将 $S$ 乘二，代价为常数 $b$ 。

求达成目的的最小代价。

输入描述:

输入共四行；

第一行一个整数 ；

第二行一个长度为  的下标从  开始的整数序列 ，整数之间用空格隔开；

第三行一个整数 ；

第四行一个长度为  的下标从  开始的  串 。

输出描述:

一个整数表示最小代价

示例1

输入

复制

输出

复制

说明

一种可能的操作方法是依次对第  位和第  位做操作一，然后做操作二，代价和为  。容易证明没有比这优的操作序列。

备注:

。