题目描述

暑假共有 $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 个整数代表答案。

5
6 2
-3 6 -1 -8 7 -6
-3 2
5 4
-9 -6 -6 -7 -8
-5 7 -9 -3
7 7
7 2 3 0 -2 4 2
-9 -2 -5 0 -7 9 -1
5 3
10 4 6 7 4
-1 -9 2
5 3
6 3 5 10 5
-8 -5 -5

20
144
-34
-12
-163

提示

对于所有数据，满足 $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$；