A - 路径

题目描述

我是所有旅程的终点。

给定两个序列 $a,b$ ，长度分别为 $n,m$ 。现在考虑一个 $n*m$ 的矩阵 $C$ 满足 $C_{i,j}=a_i+b_j$ 。

你在矩阵上散步，要从 $(1,1)$ 走到 $(n,m)$ 。每一步从 $(x,y)$ 出发可以走到 $(x',y)$ ，要求 $x'>x$ ，这一步的代价是 $|C_{x,y}-C_{x',y}|$；也可以走到 $(x,y')$ ，要求 $y'>y$ ，代价是 $|C_{x,y}-C_{x,y'}|$ 。

我们希望每一步的代价之和最大。请输出这个最大值。

输入格式

第一行输入两个整数 $n,m$ ，分别表示 $a,b$ 的长度。

输出格式

输出一行一个整数，表示此时的答案。

样例

样例输入

4 2
5 7 8 10
10 3

样例输出

12

数据范围

对于所有数据，$1\le n,m\le 10^6,1\le a_i,b_i\le 10^9$ 。

子任务 1 ( 20% ) : $1\le n,m\le 300$ 。

子任务 2 ( 30% )：$1\le n,m\le 1000$ 。

子任务 3 ( 20% ) : $1\le n,m\le 5000$ 。

子任务 4 ( 30% ) : 无特殊限制。