Description

有一块$n*m$的矩形巧克力，准备将它切成$n*m$块。巧克力上共有$n-1$条横线和$m-1$条竖线，你每次可以选择一块，沿着上面的一条横线或竖线将巧克力切开，无论切割的长短，沿着每条横线切一次的代价依次为$y_1，y_2，…，y_{n-1}$，而沿竖线切割的代价依次为$x_1$，$x_2$，…，$x_{m-1}$。 求将这块巧克力切成$n*m$块的最小代价和。

Format

Input

第一行为两个整数$n和m$。 接下来$n-1$行，每行一个整数，分别代表$x_{1}$，$x_{2}$，…，$x_{n-1}$。 接下来$m-1$行，每行一个整数，分别代表$y_{1}$，$y_{2}$，…，$y_{m-1}$。

Output

输出一整数，为切割巧克力的最小代价。

Samples

6 4
2
1
3
1
4
4
1
2

42

Limitation

$30$%的数据，$n<=100,m<=100$； $100$%的数据，$n<=10000，m<=10000$。