SP247 CHOCOLA - Chocolate

我们有一条巧克力，由$mn$个正方形小块组成。一个人需要将这条巧克力切成单个小块。每一部分的巧克力可以像图中标明的线那样，沿竖直和水平方向切开。 将巧克力沿着选中的竖直或水平方向切开，会将其分成更小的两块。每次破开一部分巧克力需要一定的代价，由一个正整数表示。这一代价并不取决于被切开的巧克力的大小，只取决于切开的边。让我们定义沿连续的水平线切开的代价为$x_1,x_2,\dots,x_{m-1}$，沿竖线切开的代价为$y_1,y_2,\dots,y_{n-1}$。 将整条巧克力切成单独的正方形小块的代价等于逐次切开的总代价。你需要计算将巧克力切成正方形小块所需的最小代价。 例如，如果我们将图中的巧克力先沿着水平线切开，然后对每一块沿着竖线切开，那么切开的代价为$y_1+y_2+y_3+4(x_1+x_2+x_3+x_4+x_5)$。 #### 任务 编写一个程序，对于**每个测试数据**： - 读入数字$x_1,x_2,\dots,x_{m-1}$和$y_1,y_2,\dots,y_{n-1} $。 - 计算将巧克力切成单独的正方形小块所需的最小代价，并输出结果。

**本题有多组数据。** 第一行给出一个数字，表示数据组数，其后跟有一行空行。数据组数不会超过$20$。 对于每一组测试数据，第一行给出两个正整数$m,n$，由空行分开，其中$2\le m,n \le 1000$。 接下来的$m-1$行，每行给出$x_1,x_2,\dots,x_{m-1}$，其中$1\le x_i \le 1000$。 接下来的$n-1$行，每行给出$y_1,y_2,\dots,y_{n-1}$，其中$1\le y_i\le 1000$。 相邻测试数据之间会有一行空行分开。

对每一组测试数据，输出一个整数，代表切开巧克力的最小代价。