#8946. 「THUPC 2025 初赛」Harmful Machine Learning 普及/提高−

人工智能领域大神 The NIT 正在训练机器人 The BOT。

The BOT 在一个 的网格上移动，其中在 上有数字 。The BOT 初始在格子 , The BOT 想要走到一个数字尽量大的格子。每一步 The BOT 可以选择移动到相邻的一个格子或是不动，并且在移动后可以选择是否选择格子上的数字并结束游戏，而为了训练 The BOT 的能力，The NIT 会给出一些阻碍，在 The BOT 选择是否结束之后，The NIT 可以将两个数字交换位置。

具体地说，我们可以把整个游戏看成若干个回合，初始 The BOT 在位置 ，在一个回合中，以下事件会按顺序依次发生：

1. The NIT 选择两个位置 ，并交换 的值，注意 可以等于 ，此时交换不会带来任何变化。
2. The BOT 选择移动到一个相邻的位置或是原地不动，令 The BOT 现在所在的位置为 ，即选择 且 ，并移动到 。
3. The BOT 选择是否结束游戏，令 The BOT 现在所在的位置为 ，如果选择结束则会获得 的分数并立刻结束游戏，否则无事发生。

可以发现，如果 The BOT 一直不选择结束游戏，则游戏永远不会结束，为了防止这个情况的发生，在游戏的第 个回合，The BOT 必须选择立刻结束游戏。

The NIT 希望 The BOT 结束游戏时的分数最小，而 The BOT 希望这个分数最大。The NIT 和 The BOT 都是绝顶聪明的，但他们并没有时间玩 个回合，于是他们请你帮他们计算一下，The BOT 最终的分数是多少？

本题含有多组测试数据。

第一行一个整数 ，表示测试数据数量。

对于每一组数据：

第一行两个正整数 ，分别表示网格的长度以及初始位置 。

之后一行 个非负整数 。

保证所有数据的 的总和不超过 。

对于每一组数据，输出一行一个数表示答案。

样例输入 1

复制4
3 2
1 2 3
13 4
1 1 4 5 1 4 1 9 1 9 8 1 0
4 2
1 10 100 1000
1 1
114514

样例输出 1

复制3
4
100
114514

题目来源

题目来自 THUPC2025（2025年清华大学学生程序设计竞赛暨高校邀请赛）初赛，信息来源于 THUSAAC 仓库。