题目描述

暑假共有 $𝑛$ 天，第 $𝑖$ 天的精力指数为 $𝑎[𝑖]$，你想要利用假期依次（按 $1,2, \dots , 𝑚$ 顺序） 复习 $𝑚$ 门功课，第 $𝑖$ 门功课的重要程度为 $𝑏[𝑖]$，且每门功课的复习时段必须连续，并且不能有某天不干事。

假设第 $𝑖$ 门功课的复习时段为第 $𝑙 \sim 𝑟$ 天，那么第 $𝑖$ 门功课的收益为 $𝑏[𝑖] × (𝑎[𝑙] +𝑎[𝑙 + 1]+ \dots +𝑎[𝑟])$，你的总收益为 $𝑚$ 门功课收益的总和。

请你制订一个复习计划，使得总收益最大。

形式化地，给定序列 $a[1 \sim 𝑛], b[1 \sim 𝑚]$，你需要把 $1,2, . . . , 𝑛$ 这个序列分成首尾相连且非空的 $𝑚$ 段，假设每段的 $𝑎$ 之和为 $𝑠[1 ∼ 𝑚]$，最大化 $\sum_{i=1}^m b[𝑖] \times 𝑠[𝑖]$ 的值。

例如 $𝑎 = [−3,6, −1, −8,7, −6], 𝑏 = [−3,2]$，最优策略是第 $1 ∼ 4$ 天复习第 $1$ 门功课，收益为 $−3 × (−3 + 6 − 1 − 8) = 18$；第 $5 \sim 6$ 天复习第 $2$ 门功课，收益为 $2 \times (7 − 6) = 2$；总收益为 $18 + 2 = 20$。 例如 $𝑎 = [6,3,5,10,5], 𝑏 = [−8, −5, −5]$，最优策略是分成 $[1], [2,3,4], [5]$ 三段，总收益为 $−8 \times 6 \times 5 \times (3 + 5 + 10) − 5 \times 5 = −163$。

输入描述

第一行 $1$ 个整数 $𝑇$，代表有 $𝑇$ 组数据。

每组数据共三行，第一行有 $2$ 个正整数 $𝑛, 𝑚$，表示暑假的天数和需要复习的功课数量。

第二行有 $𝑛$ 个整数 $𝑎[1 \sim 𝑛]$，其中 $a[i]$ 表示第 $i$ 天的精力指数。

第三行有 $𝑚$ 个整数 $𝑏[1 \sim 𝑚]$，其中 $b[i]$ 表示第 $i$ 门功课的重要程度。

输出描述

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

输入样例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

输出样例1

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$。