题目描述

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

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

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

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

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

例如 $𝑎 = [6,3,5,10,5], 𝑏 = [−8, −5, −5]$，最优策略是分成 $[1],[2,3,4],[5]$ 三段，总收益为 $−8 × 6 − 5 × (3 + 5 + 10) − 5 × 5 = −163$。

输入格式

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

每组数据第一行 $2$ 个整数 $𝑛, 𝑚$，第二行 $𝑛$ 个整数 $𝑎[1 ∼ 𝑛]$，第三行 $𝑚$ 个整数 $𝑏[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

20
144
-34
-12
-163

数据范围

对于所有数据，满足 $1 ≤ 𝑇 ≤ 20,1 ≤ 𝑚 ≤ 𝑛 ≤ 2000, −10^3 ≤ 𝑎[𝑖], 𝑏[𝑖] ≤ 10^3$。

对于测试点 $1\sim 7$：$𝑛 ≤ 10$。

对于测试点 $8\sim 12$：$𝑛 ≤ 500$。

对于测试点 $13\sim 16$：所有 $𝑎[𝑖], 𝑏[𝑖]$ 为正整数。

对于测试点 $17\sim 20$：$𝑛 ≤ 2000$。