分数: 500 点
问题陈述
在 xy 平面,在满足以下条件的区域中 0 ≤ x ≤ W, 0 ≤ y ≤ H,每个点都有一所房子, x 和 y 是整数。
每对点之间都有未铺砌的道路,其中任一 x 坐标相等并且之间的差 y 坐标是 1,或 y 坐标相等并且之间的差 x 坐标是 1.
在坐标上的房屋之间铺路的成本 (i,j) 和 (i+1,j) is p_i 对于任何值 j,而在坐标上的房屋之间铺路的成本 (i,j) 和 (i,j+1) is q_j 对于任何值 i.
高桥先生想要铺设其中一些道路,并且只能在铺设的道路上在任意两栋房屋之间行驶。找出总成本最小的解决方案。
约束
- 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