Migrated from Lutece 1289 喵哈哈村的编码

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

编码特别的有趣，特别是在喵哈哈村里的编码。

因为喵哈哈村的对编码有一些特别的限制。

假设某一个编码为$S_{1},S_{2},S_{3},S_{4}....,S_{l}$，其中$S_{i}$表示这是编码中的第$i$位。

那么在喵哈哈村中，它应该满足以下要求：

1. $l$ 不应该超过$m$，即编码的长度不超过$m$
2. 每一个位置$S_{i}$的取值范围为$[1,r_i]$

对于所有的编码而言，应该满足任意一个编码都不是另外一个编码的前缀。

现在你就需要在满足以上条件的情况下，构造出$n$个编码，使得$\sum_{i=1}^{n}w_{i}l_{i}$ 最小。

$l_{i}$即第$i$个编码的长度。

Input

第一行两个整数 $n$,$m$($1<=n,m<=500$)

第二行$n$个整数$w_{1},w_{2}......w_{n}$($1<=wi<=500$)

第三行$m$个整数$r_{1},r_{2}.....r_{m}$($1<=ri<=500$}

保证$r_{1},r_{2}.....r_{m}$的乘积大于等于$n$

Output

一个整数，表示最小值是多少。

Samples

2 2
4 3
2 1

7

3 2
1 2 4
2 2

10

Note

第一个样例的两个编码为：{1}，{2}，答案就是4+3=7

第二个样例的三个编码为：{1,1}，{1,2}，{2}，答案就是2*1+2*2+4 = 10

Resources

每周一题 div1