时间限制:1000ms  空间限制:256MB

题目描述

在他们带回的礼物中，有一盒神奇的巧克力。他们打算在和往日的老同学一起观看电影《我和我的祖国》时分而食之。这是一块 n* m的矩形巧克力，所以快乐准备将它切成 n* m 块。由于这块巧克力是一块魔法巧克力，所以必须按照特殊的方法进行切割。巧克力上共有n-1 条横线和 m-1 条竖线，每次快乐可以沿着其中的一条线切开某一块。而且这样切一次的代价只跟所切的线有关，而与所切的长度无关。沿着每条横线切一次的代价依次为 y1，y2，……yn-1，竖线为 x1，x2，……xm-1。例如，对于图中的巧克力，我们先沿着 3 条横线切，再沿 5 条竖线切，最终代价为 y1+y2+y3+4*(x1+x2+x3+x4+x5)

快乐想知道，他怎样切才能使代价最小。

输入格式

共 3 行：第一行为两个正整数 n 和 m；第二行有 n-1 个正整数，分别代表$y_1，y_2，……y_{n-1}$；第 3 行有 m-1 个正整数，分别代表 $x_1，x_2，……，x_{m-1}$。

输出格式

一行，一个整数，表示最小代价。

样例

输入#1

6 4 
2 1 3 1 4 
4 1 2

输出#1

42

数据范围/约定

40%的数据，1<=n,m<=100，100%的数据，1<=n,m<=10000；

结果在 int 范围以内。