暑假共有 $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$。
## Input
第一行 1 个整数 $T$，代表有 $T$ 组数据。
每组数据第一行 2 个整数 $n, m$，第二行 $n$ 个整数 $a[1 \sim n]$，第三行 $m$ 个整数 $b[1 \sim m]$。
## Output
输出 $T$ 行，每行 1 个整数代表答案。
[samples]
## Note
对于所有数据，满足 $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$；