1230 : 最大路径

Description

给定长度为 \(n\) 的数组 \(a\) 和长度为 \(m\) 的数组 \(b\)，定义一个大小为 \(n \times m\) 的网格，其中单元格 \((x,y)\) 的值表示为 \(C[x,y]=a_x + b_y\)。

你要从 \((1,1)\) 开始，每一步可以选择移动到位于当前位置右下的某个网格，直到到达\((n,m)\)，目标是最大化路径上相邻单元格之间绝对差值的和。

具体而言，你的目标是找到一个满足以下条件的序列 \((x_1,y_1), (x_2,y_2), ..., (x_k,y_k)\)：

• \((x_1,y_1) = (1,1)\)
• \((x_k,y_k) = (n,m)\)
• \(x_i \le x_{i+1},\ y_i \le y_{i+1},\ (x_i,y_i) \neq (x_{i+1},y_{i+1})\ \forall i\in [1, k)\)

同时最大化 \(\sum_{i=1}^{k-1} {|C[x_i,y_i]-C[x_{i+1},y_{i+1}]|}\)。

Input

第一行包含两个整数 \(n, m\ (1\le n,m \le 10^5)\)。

第二行包含 \(n\) 个整数，表示数组 \(a\ (1\le a_i\le 10^5)\)。

第三行包含 \(m\) 个整数，表示数组 \(b\ (1\le b_i\le 10^5)\)。

Output

输出一行包含一个整数，表示答案。

Sample

4 4
1 3 3 1
8 10 8 5
##CASE##
4 2
5 7 8 10
10 3

11
##CASE##
12

Hint

Source

Author

SYSU