Description

你要从(0,0)点走到(n,m)，每次只能往x轴或者y轴正方向移动一个单位距离。

从(i,j)移动到(i,j+1)的代价为ri,从(i,j)移动到(i+1,j)的代价为cj。

求最小代价。

Format

Input

第一行两个正整数n,m

第二行n+1正整数表示ri,第三行m+1个正整数表示ci。

n，m<=10^5,0<ri,ci<=10^8。

Output

一行一个整数，表示答案。

Samples

2 3
5 3 7
7 2 5 6

19