题目描述

在一个$xy$平面上，有一片满足$0≤x≤W, 0≤y≤H$的区域，每个整数坐标$(x, y)$上都有一个房子。

任意一对房子之间都有未铺设的道路，其中要么$x$坐标相等且$y$坐标相差为$1$，要么$y$坐标相等且$x$坐标相差为$1$。

对于任意给定的$j$值，铺设连接坐标$(i,j)$和$(i+1,j)$上的道路的成本为$p_i$；对于任意给定的$i$值，铺设连接坐标$(i,j)$和$(i,j+1)$上的道路的成本为$q_j$。

高桥先生希望铺设一些道路，以便只能通过铺设的道路在任意两个房子之间旅行。找到总成本最小的方案。

约束条件

• $1≦W,H≦10^5$
• $1≦p_i≦10^8(0≦i≦W-1)$
• $1≦q_j≦10^8(0≦j≦H-1)$
• $p_i(0≦i≦W−1)$是整数。
• $q_j(0≦j≦H−1)$是整数。

输入

从标准输入中以以下形式给出输入。

$W$ $H$ $p_0$ : $p_{W-1}$ $q_0$ : $q_{H-1}$

输出

输出一个表示总成本最小值的整数。

示例输入 1

2 2
3
5
2
7

示例输出 1

29

只需铺设以下八条道路即可。

• 连接坐标$(0,0)$和$(0,1)$的道路
• 连接坐标$(0,1)$和$(1,1)$的道路
• 连接坐标$(0,2)$和$(1,2)$的道路
• 连接坐标$(1,0)$和$(1,1)$的道路
• 连接坐标$(1,0)$和$(2,0)$的道路
• 连接坐标$(1,1)$和$(1,2)$的道路
• 连接坐标$(1,2)$和$(2,2)$的道路
• 连接坐标$(2,0)$和$(2,1)$的道路

示例输入 2

4 3
2
4
8
1
2
9
3

示例输出 2

60