题目描述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

出题Author

SYSU

来源Source

第九届中国大学生程序设计竞赛（秦皇岛）-（CCPC2023-Qinhuangdao）