← 返回题目列表

AtCoder · codefestival_2016_qualB_c

C. 网格 MST

中文机器翻译题面 查看原题

分数: 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