B4172 [BCSP-X 2024 6 月小学高年级组] 学习计划

暑假共有 $n$ 天，第 $i$ 天的精力指数为 $a[i]$，你想要利用假期**依次（按 $1, 2, \ldots, m$ 顺序）** 复习 $m$ 门功课，第 $i$ 门功课的重要程度为 $b[i]$，且**每门功课的复习时段必须连续，并且不能有某天不干事。** 假设第 $i$ 门功课的复习时段为第 $l \sim r$ 天，那么第 $i$ 门功课的收益为 $b[i] \times (a[l] + a[l + 1] + \ldots + a[r])$，你的总收益为 $m$ 门功课收益的总和。 请你制订一个复习计划，使得总收益最大。 形式化地，给定序列 $a[1 \sim n], b[1 \sim m]$，你需要把 $1, 2, \ldots, n$ 这个序列分成首尾相连且非空的 $m$ 段，假设每段的 $a$ 之和为 $s[1 \sim m]$，最大化 $\sum_{i=1}^{m} b[i] \times s[i]$ 的值。 例如 $a = [-3, 6, -1, -8, 7, -6], b = [-3, 2]$，最优策略是第 $1 \sim 4$ 天复习第 $1$ 门功课，收益为 $-3 \times (-3 + 6 - 1 - 8) = 18$；第 $5 \sim 6$ 天复习第 $2$ 门功课，收益为 $2 \times (7 - 6) = 2$；总收益为 $18 + 2 = 20$。 例如 $a = [6, 3, 5, 10, 5], b = [-8, -5, -5]$，最优策略是分成 $[1], [2, 3, 4], [5]$ 三段，总收益为 $-8 \times 6 - 5 \times (3 + 5 + 10) - 5 \times 5 = -163$。

第一行 1 个整数 $T$，代表有 $T$ 组数据。 每组数据第一行 2 个整数 $n, m$，第二行 $n$ 个整数 $a[1 \sim n]$，第三行 $m$ 个整数 $b[1 \sim m]$。

输出 $T$ 行，每行 1 个整数代表答案。

对于所有数据，满足 $1 \leq T \leq 20, 1 \leq m \leq n \leq 2000, -10^3 \leq a[i], b[i] \leq 10^3$。 - 对于测试点 1~7：$n \leq 10$； - 对于测试点 8~12：$n \leq 500$； - 对于测试点 13~16：所有 $a[i], b[i]$ 为正整数； - 对于测试点 17~20：$n \leq 2000$；