#547. 【2024-11-22 P1】A - 路径

【2024-11-22 P1】A - 路径

A - 路径

题目描述

我是所有旅程的终点。

给定两个序列 a,ba,b ,长度分别为 n,mn,m 。现在考虑一个 n∗mn*m 的矩阵 CC 满足 Ci,j=ai+bjC_{i,j}=a_i+b_j 。

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

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

输入格式

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

输出格式

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

样例

样例输入

4 2
5 7 8 10
10 3

样例输出

12

数据范围

对于所有数据,1≤n,m≤106,1≤ai,bi≤1091\le n,m\le 10^6,1\le a_i,b_i\le 10^9 。

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

子任务 2 ( 30% ):1≤n,m≤10001\le n,m\le 1000 。

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

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