D. 避雨

题目描述

今天是个雨天，Lay 博士遇到了一道难题。有 $N$ 头奶牛（编号 $1\sim N$）不喜欢被淋湿，它们站成一排，在 Lay 博士的农场里等待 Lay 博士给它们买伞遮雨。Lay 博士农场的宽度为 $M$。第 $i$ 头奶牛站在 $X_i$ 的位置（$1\le X_i\le M$）。一把能遮挡位置 $a$ 到位置 $b$ 的伞需要的宽度为 $(b-a+1)$。

Lay 博士决定去小C杂货店买特制的伞。杂货店一共有 $M$ 种伞（每种伞都有充足的货），每种伞对应的宽度分别为 $1\sim M$。每种伞都有一个价格 $c_i$（$1\le c_i\le 1000000$）。宽度大的伞价格不一定比宽度小的伞价格高。

帮助 Lay 博士出使每只奶牛都能避雨的最小花费。 伞可以有重叠的部分。

输入格式

第一行两个整数 $N(1\le N\le 5000), M(1\le M\le 100000)$。 接下来 $N$ 个数，第 $i$ 个数表示 $X_i$。 接下来 $M$ 行，第 $i$ 行表示 $c_i$。

输出格式

输出一个数，表示满足要求的最小花费。

样例

输入

6 12
1 2 11 8 4 12
2 3 4 8 9 15 16 17 18 19 19

输出

9

样例解释

最后的方案需要一把宽度为 $4$，宽度为 $1$，宽度为 $2$ 的伞，花费为 $4+2+3=9$。

数据范围与提示

• $1 \le N \le 5000$
• $1 \le M \le 100000$
• $1 \le c_i \le 1000000$