T827096 候晴行程（travel）

一支运输队要从城镇 $0$ 出发，依次经过城镇 $1,2,\ldots,N$，最终到达城镇 $N$。城镇 $i-1$ 与城镇 $i$ 之间的道路长度为 $D_i$。 运输队必须在接下来的 $M$ 天内完成行程。每天只能选择下列一种行动： - 在当前城镇等待一天，不产生费用； - 用一天时间走完通向下一个城镇的道路。 天气会影响运输费用。已知第 $j$ 天的天气系数为 $C_j$。如果第 $j$ 天走第 $i$ 段道路，就产生 $D_i\times C_j$ 的费用。 道路必须按编号从小到大依次经过，一天不能经过两段道路。运输队可以在出发前或途中的城镇等待，也可以提前到达终点。 请你安排每天的行动，使运输队在 $M$ 天内到达城镇 $N$，并求总费用的最小值。 本题有多组测试数据，各组互不影响。

第一行包含一个整数 $T$，表示测试数据组数。 对于每组测试数据： - 第一行包含两个整数 $N,M$。 - 接下来 $N$ 行，第 $i$ 行包含一个整数 $D_i$，表示第 $i$ 段道路的长度。 - 接下来 $M$ 行，第 $j$ 行包含一个整数 $C_j$，表示第 $j$ 天的天气系数。

对于每组测试数据，输出一行一个整数，表示完成行程的最小总费用。

### 样例解释 可以在第 $1$ 天等待，第 $2$ 天走第一段道路，第 $3$ 天走第二段道路，第 $4$ 天等待，第 $5$ 天走第三段道路。 总费用为 $10\times30+25\times15+15\times30=300+375+450=1125$。可以证明，不存在总费用更小的合法行程。 ## 样例 2 见 `考生目录/travel/travel2.in` 与 `考生目录/travel/travel2.ans`。该样例满足测试点 $1\sim6$ 的约束。 ## 样例 3 见 `考生目录/travel/travel3.in` 与 `考生目录/travel/travel3.ans`。该样例满足测试点 $7\sim10$ 的约束。 ## 样例 4 见 `考生目录/travel/travel4.in` 与 `考生目录/travel/travel4.ans`。该样例满足测试点 $11\sim20$ 的约束。 ## 样例 5 见 `考生目录/travel/travel5.in` 与 `考生目录/travel/travel5.ans`。该样例满足测试点 $11\sim20$ 的约束。 ## 样例 6 见 `考生目录/travel/travel6.in` 与 `考生目录/travel/travel6.ans`。该样例满足测试点 $11\sim20$ 的约束。 ## 数据范围 对于所有数据，保证： - $1\le T\le10$； - 每组数据中，$1\le N\le M\le1000$，$1\le D_i,C_j\le1000$； - 同一输入文件中，所有组的 $N\times M$ 之和不超过 $2\times10^6$； - 所有输入均为整数。 | 测试点编号 | 附加限制（每组均满足） | | ---------- | ---------------------- | | $1\sim6$ | $M\le18$ | | $7\sim10$ | $N=M$ | | $11\sim20$ | 无 |