[CSP-S2019 江西] 网格图

题目背景

JXCSP-S T3

题目描述

给定一个 $n\times m$ 的网格图,行从 $1\sim n$ 编号,列从 $1\sim m$ 编号,每个点可用它所在的行编号 $r$ 与所在的列编号 $c$ 表示为 $(r, c)$。 点 $(i,j)$ 与 $(i,j+1)$ 间连有一条权值为 $a_i$ 的边,其中 $1\le i\le n, 1\le j<m$。 点 $(i, j)$ 与 $(i+1,j)$ 间连有一条权值为 $b_j$ 的边,其中 $1\le i< n, 1\le j \le m$。 请你求出这个网格图的最小生成树。

输入输出格式

输入格式


第一行两个正整数 $n, m$ 表示行数与列数。 第二行 $n$ 个正整数表示 $a_i$。 第三行 $m$ 个正整数表示 $b_j$。

输出格式


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

输入输出样例

输入样例 #1

3 3
2 4 3
1 3 2

输出样例 #1

16

说明

#### 【输入输出样例 1 说明】 最小生成树中的边包括:第一行上的所有边,第一列、第二列、第三列上的所有边。 #### 【数据规模与约定】 对于 $20\%$ 的数据,$n, m\le 3 , a_i, b_j \le 10$; 对于 $40\%$ 的数据,$n, m\le 20 , a_i, b_j\le 100$; 对于 $64\%$ 的数据,$n, m\le 300 , a_i, b_j\le 1000$; 对于 $100\%$ 的数据:$3\le n, m \le 3\times 10^5 , 1 \le a_i, b_j\le 10^5$。