配点: 100 点
問題
在现在的哈萨克斯坦境内,曾经有一条贸易路线,被称为“丝绸之路”。
丝绸之路上 从西边开始有 N + 1 个城市。 它的编号为 0, 都市 1, \ldots, 都市 N 。城市 i - 1 和城市 i ( 之间的距离1 \leqq i \leqq N)是 D_i 。
JOI,一个交易者,是一座城市 从 0 出发,依次经过城市, 决定将丝绸运至 N 。城市 0 来自城市 直到 N 您必须在 M 天内搬家。 JOI君每天都会进行以下的活动。 2 以下任何一项 1 选择一项。
- 移动:从当前城市 1 前往东部城市 1 行程需要一天时间。当前城市 i - 1 (1 \leqq i \leqq N),如果您在城市 移至 i 。
- 等待:不要移动并留在您当前所在的城市。 等待 1 天。
移动很困难,每次移动都会增加疲劳感。丝绸之路上的天气一天天变化,天气越恶劣,出行就越困难。
JOI 你可以用它来携带丝绸。 M 过几天 j 日目 (1 \leqq j \leqq M) 的恶劣天气是 我们知道 C_j 。城市 i - 1 来自城市 直到 i (1 \leqq i \leqq N)到 j 日目 (1 \leqq j \leqq M),疲劳程度为 仅 D_i \times C_j 累积。当您不移动和等待的日子里,疲劳不会累积。
JOI 您希望通过明智地选择每天的行动来尽可能多地活动而不积累疲劳。和你打交道 M 天内所在城市 当移动到 N 时,求出从移动开始到结束累积的总疲劳量的最小值。
入力
输入是 由 1 + N + M 行组成。 在
1 行中,2 整数 N, M (1 \leqq N \leqq M \leqq 1\,000)以空格作为分隔符。这是因为丝绸之路 它由 N + 1 城市组成,JOI让丝绸变成城市。 表示该商品必须在 0 来自城市 直到 N 您必须在 M 天内交付。
继续 N 行 i 行目 (1 \leqq i \leqq N) 是一个整数 D_i (1 \leqq D_i \leqq 1\,000)被写入。这是一座城市 i - 1 和城市 i 之间的距离是 D_i 。
继续 M 行 j 行目 (1 \leqq j \leqq M) 是一个整数 C_j (1 \leqq C_j \leqq 1\,000)被写入。这是j 当天天气不好 C_j 。
出力
JOI Kimiga 移动到 M 天内所在城市 当移动到 N 时,计算从移动开始到结束累计的总疲劳度的最小值。 在 1 行。
入力例 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