CSG-CPC
Online Judge

1230 : 最大路径

         Time Limit: 1 Sec     Memory Limit: 256 Mb     Submitted: 35     Solved: 22    

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