Public Judge

pjudge

Time Limit: 2 s Memory Limit: 512 MB Total points: 100 Hackable ✓

# 21625. 【PR #3】最小生成树

统计

有一张 $n\times m$ 的网格图,第 $x$ 行第 $y$ 列的格点记为 $(x,y)$,给定四个单调不降数组 $A,B,C,D$,网格图的边权由这四个数组决定,具体的:

  • $(x,y)$ 和 $(x+1,y)$ 之间的边权为 $A_x+B_y$。
  • $(x,y)$ 和 $(x,y+1)$ 之间的边权为 $C_x+D_y$。

你需要求出这张网格图最小生成树的大小。

输入格式

第一行两个整数 $n,m$ 表示网格图大小。

第二行 $n-1$ 个整数 $A_i$ 表示数组 $A$。

第三行 $m$ 个整数 $B_i$ 表示数组 $B$。

第四行 $n$ 个整数 $C_i$ 表示数组 $C$。

第五行 $m-1$ 个整数 $D_i$ 表示数组 $D$。

输出格式

一行一个整数表示最小生成树大小。

样例一

input

2 3
1
1 3 6
1 4
1 2

output

17

explanation

最小生成树包含如下五条边:

  • $(1,1) - (2,1): 2$
  • $(1,1) - (1,2): 2$
  • $(1,2) - (1,3): 3$
  • $(1,2) - (2,2): 4$
  • $(2,2) - (2,3): 6$

样例二

见下发文件。

数据范围与提示

对于所有数据,保证 $2\leq n,m\leq 10^5, 1\leq A_i,B_i,C_i,D_i\leq 10^6$。

保证 $A_i\leq A_{i+1}, B_i\leq B_{i+1}, C_i\leq C_{i+1}, D_i\leq D_{i+1}$。

测试点编号 $n,m\leq$ 特殊性质
$1\sim 6$ $10^3$
$7\sim 12$ $10^5$ 存在 $x,y$ 满足 $A_i=x,B_i=y$,即 $A,B$ 数组中所有元素相同
$13\sim 20$

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$