Bobo 学习了哈夫曼编码，并尝试增加了一些限制。

Bobo 有 $n$ 个单词需要编码。第 $i$ 个单词的权重为 $w_i$。他想将第 $i$ 个单词编码为序列 $S_i = (s_{i,1}, s_{i,2}, \dots, s_{i,l_i})$，其中：

1. $1 \le l_i \le m$。
2. 给定 $r_1, r_2, \dots, r_m$，对于所有 $1 \le j \le l_i$，满足 $1 \le s_{i,j} \le r_j$。
3. 对于所有 $i \neq j$，$S_i$ 不是 $S_j$ 的前缀。

注意，序列 $A = (a_1, a_2, \dots, a_k)$ 是序列 $B = (b_1, b_2, \dots, b_l)$ 的前缀，当且仅当 $k \le l$ 且 $a_1 = b_1, a_2 = b_2, \dots, a_k = b_k$。

Bobo 想要求出 $\sum_{1 \le i \le n} w_i \cdot l_i$ 的最小值。

输入格式

第一行包含 2 个整数 $n, m$ ($1 \le n, m \le 500$)。 第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 500$)。 第三行包含 $m$ 个整数 $r_1, r_2, \dots, r_m$ ($1 \le r_i \le 500$)。 保证 $r_1 \cdot r_2 \cdot \dots \cdot r_m \ge n$。

输出格式

输出一个整数，表示最小值。

样例

输入 1

2 2
4 3
2 1

输出 1

7

输入 2

3 2
1 2 4
2 2

输出 2

10