#P16156. [2022国家队训练南京站]T3

[2022国家队训练南京站]T3

题目描述

Alice 和 Bob 在玩游戏。

有一个 n×mn\times m 大小的棋盘,棋盘的第 xx 行第 yy 列记为 (x,y)(x,y)。

开始时棋盘上有一个车位于 (1,1)(1,1)。Alice 和 Bob 轮流操作,Alice 先操作。对于每次操作,玩家都有两种选择:

  1. 将车移动至同行或同列的某个格子上,注意不能移动到车本来所在的格子。换句话说,若车当前位于 (x,y)(x,y),则它可被移动至 (c,y) (1≤c≤n,c≠x)(c,y)\ (1\leq c\leq n,c\neq x) 或 (x,d) (1≤d≤m,d≠y)(x,d)\ (1\leq d\leq m,d\neq y)。
  2. 结束游戏。

Alice 和 Bob 发现这个游戏可能永远不会结束,于是他们规定在任意时刻,每个格子被车移动到的次数要严格小于 10910^9。注意,开始时格子 (1,1)(1,1) 算作被移动到一次。

只是单纯地移动棋子非常无聊,所以他们给出了两个分别长为 n,mn,m 的序列 a,ba,b。结束游戏时,若车当前位于 (x,y)(x,y),则游戏的分数为 ax+bya_x+b_y,Alice 想让游戏的分数尽量小,而 Bob 想让游戏的分数尽量大。你需要求出在双方的最优策略下,游戏的分数是多少。

输入格式

第一行两个整数 n,mn,m 表示棋盘大小。

第二行 nn 个整数 aia_i,表示序列 aa。

第三行 mm 个整数 bib_i,表示序列 bb。

输出格式

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

样例

样例输入 1

2 1
3 2
2

样例输出 1

4

样例输入 2

6 7
4 5 6 1 2 3
5 2 1 3 4 6 7

样例输出 2

7

样例解释

样例 11 中如果双方要移动,那么目标都是唯一确定的,而 Bob 在他的第 109−110^9-1 轮中移动时发现此时会将格子 (1,1)(1,1) 经过的次数变为 10910^9,而这不是合法的操作。所以 Bob 只能在他的某次操作中选择结束游戏,游戏的分数即为 a2+b1=4a_2+b_1=4。

样例 22 的决策树大小至少为 51095^{10^9} 量级,这里空太小,画不开。

数据范围

对于所有数据,1≤n,m≤2×1051\leq n,m\leq 2\times 10^5,1≤ai,bi≤1081\leq a_i,b_i\leq 10^8。

  • 子任务 11(1414 分):n,m≤4n,m\leq 4。
  • 子任务 22(1111 分):bi=1b_i=1。
  • 子任务 33(1515 分):n,m≤10n,m\leq 10。
  • 子任务 44(1616 分):n,m≤103n,m\leq 10^3。
  • 子任务 55(1919 分):n,m≤5×104n,m\leq 5\times 10^4。
  • 子任务 66(2525 分):无特殊限制。