某市有一条笔直的景观大道，其位置坐标区间为 1 到 M。（景观大道可视为一条整数数轴，坐标均为整数）

为了美化城市夜景，市政部门在景观大道的特定位置安置了 N 个景观雕塑。第 i 个雕塑所在的坐标为 X_i。

现在需要在景观大道上安装若干盏路灯，以确保每个雕塑都能被路灯的光照覆盖。关于路灯的安装与成本，规定如下：

1. 一盏路灯可以覆盖一段连续的整数坐标区间。如果一盏路灯覆盖的起始坐标为 u，终止坐标为 v（u \le v），则其覆盖宽度 W = v - u + 1。
2. 市场上有多种规格的路灯可供选择。安装一盏覆盖宽度为 W 的路灯，其成本为 C_W。
3. 特别注意：由于生产工艺和库存清仓等因素，覆盖宽度较大的路灯，其单价并不一定比宽度较小的路灯贵。在实际规划中，若安装了宽度为 W 的路灯，不要求路灯光照覆盖到的每个整数位置上都有雕塑。同一个雕塑被多个路灯的光照覆盖到，也是允许的。

请你计算，为了使所有 N 个雕塑都处于路灯照射范围内，最少需要花费多少安装成本。

第一行包含两个由空格隔开的整数 N 和 M，分别表示雕塑的总数和景观大道的最大坐标。

接下来 N 行，每行包含一个整数 X_i，表示第 i 个雕塑所在的坐标位置。

接下来 M 行，每行包含一个整数 C_j，表示安装覆盖宽度为 j 的路灯所需的费用（第 1 行对应 C_1，第 2 行对应 C_2，以此类推）。

输出一行一个整数，表示覆盖所有雕塑的最低总成本。

样例 1 说明

雕塑位于坐标 {1, 2, 4, 8, 11, 12}。

一种最优的安装方案是：

• 安装一盏宽度为 4 的路灯，覆盖区间 [1, 4]，覆盖了坐标为 1, 2, 4 的雕塑，费用为 C_4 = 4。
• 安装一盏宽度为 1 的路灯，覆盖区间 [8, 8]，覆盖了坐标为 8 的雕塑，费用为 C_1 = 2。
• 安装一盏宽度为 2 的路灯，覆盖区间 [11, 12]，覆盖了坐标为 11, 12 的雕塑，费用为 C_2 = 3。 总费用为 4 + 2 + 3 = 9。

数据范围

对于 20\% 的数据，满足 1 \le N \le 10，1 \le M \le 30。

对于 30\% 的数据，满足 1 \le N \le 50，1 \le M \le 100。

对于 40\% 的数据，满足 1 \le N \le 100，1 \le M \le 500。

对于 100\% 的数据，满足 1 \le N \le 5000，1 \le M \le 10^5，N \lt M，1 \le C_j \le 10^6，1 \le X_i \le M。

测试数据保证所有的 X_i 互不相等，即：不存在两个雕塑，在同一个位置上的情况。

月赛26年2月动态规划