题目描述

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

你从 $(1, 1)$ 开始，在每一步中选择一个位于当前所在格子的右下方的格子，然后移动到你选择的格子，直到你到达 $(n, m)$，目标是最大化路径上相邻单元格之间差的绝对值的总和。

形式上，你的目标是找到一个序列 $(x_1, y_1), (x_2, y_2), \ldots, (x_k, y_k)$，满足以下条件：

• $(x_1, y_1) = (1, 1)$
• $(x_k, y_k) = (n, m)$
• $\forall i \in [1, k)$，有 $x_i \leq x_{i+1}, y_i \leq y_{i+1}, (x_i, y_i) \neq (x_{i+1}, y_{i+1})$
• 最大化 $\sum_{i=1}^{k-1} |C[x_i, y_i] - C[x_{i+1}, y_{i+1}]|$

输入格式

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

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

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

输出格式

一行一个整数，表示答案。

4 4
1 3 3 1
8 10 8 5

11

4 2
5 7 8 10
10 3

12