问题

在现今的哈萨克斯坦地区，古代存在着一条被称为“丝绸之路”的贸易路线。

丝绸之路上有 $N + 1$ 个城市，从西向东依次编号为城市 $0$, 城市 $1$, $\ldots$, 城市 $N$。城市 $i - 1$ 和城市 $i$ 之间的距离 ($1 \leq i \leq N$) 是 $D_i$。

商人 JOI 出发自城市 $0$，按照顺序途经各个城市，将丝绸运送到城市 $N$。他必须在 $M$ 天内完成从城市 $0$ 到城市 $N$ 的移动。JOI 在每一天都可以选择以下两种行动之一：

• 移动：从当前所在城市向东移动一个城市，需要花费一天时间。如果当前在城市 $i - 1$ ($1 \leq i \leq N$)，则移动到城市 $i$。
• 等待：不进行移动，停留在当前城市一天。

移动是困难的，每次移动都会增加 JOI 的疲劳。丝绸之路每天都会发生天气变化，天气越差，移动就越困难。

已知 JOI 可以使用 $M$ 天中的第 $j$ 天 ($1 \leq j \leq M$) 的天气情况为 $C_j$。如果在第 $j$ 天（$1 \leq j \leq M$）从城市 $i - 1$ 移动到城市 $i$，则会增加疲劳度 $D_i \times C_j$。不进行移动而等待的一天不会增加疲劳度。

JOI 希望通过巧妙选择每一天的行动，尽量减少疲劳度进行移动。请计算 JOI 在 $M$ 天内从城市 $0$ 移动到城市 $N$ 时，从开始移动到结束期间累积的疲劳度之和的最小值。

输入

输入共有 $1 + N + M$ 行。

第 $1$ 行包含 $2$ 个整数 $N, M$ ($1 \leq N \leq M \leq 1,000$)，以空格分隔。表示丝绸之路上有 $N + 1$ 个城市，JOI 必须在 $M$ 天内将丝绸运送从城市 $0$ 运送到城市 $N$。

接下来的 $N$ 行中的第 $i$ 行 ($1 \leq i \leq N$) 包含一个整数 $D_i$ ($1 \leq D_i \leq 1,000$)，表示城市 $i - 1$ 和城市 $i$ 之间的距离为 $D_i$。

接下来的 $M$ 行中的第 $j$ 行 ($1 \leq j \leq M$) 包含一个整数 $C_j$ ($1 \leq C_j \leq 1,000$)，表示第 $j$ 天的天气情况为 $C_j$。

输出

输出 JOI 在 $M$ 天内从城市 $0$ 移动到城市 $N$ 时，从开始移动到结束期间累积的疲劳度之和的最小值，以一行输出。

输入示例 1

3 5
10
25
15
50
30
15
40
30

输出示例 1

1125

在输入示例 1 中，为了使累积的疲劳度最小化，JOI 可以按以下方式移动：

• 第 $1$ 天等待。
• 第 $2$ 天从城市 $0$ 移动到城市 $1$。此时累积的疲劳度为 $10 \times 30 = 300$。
• 第 $3$ 天从城市 $1$ 移动到城市 $2$。此时累积的疲劳度为 $25 \times 15 = 375$。
• 第 $4$ 天等待。
• 第 $5$ 天从城市 $2$ 移动到城市 $3$。此时累积的疲劳度为 $15 \times 30 = 450$。

在这种移动方式下，JOI 的累积疲劳度为 $300 + 375 + 450 = 1,125$，这是最小值。

输入示例 2

2 6
99
20
490
612
515
131
931
1000

输出示例 2

31589