AT_ijpc2015_e.カードゲーム

Snuke 和 Sumeko 玩了一个用带数字的卡片和硬币进行的游戏。

起初，Snuke 拿着一张写有数字 $ T $ 的卡片和 $ K $ 枚硬币，而 Sumeko 拥有 $ N $ 张未展示的卡片。
游戏共进行 $ N $ 个回合，每个回合按照如下步骤进行：

• Sumeko 从未展示的卡片中选一张展示给 Snuke，卡片上的数字记为 $ A $。
• 然后 Snuke 参照他手中卡片上的数字 $ B $，会受到 $ |A - B| $ 的伤害。
• 如果 Snuke 还有硬币，他可以选择用一枚硬币将手中的卡片与展示的卡片交换，或者选择不换卡片。

在这个游戏中，Snuke 希望尽可能减小每个回合中所受伤害的最大值。经过观察，Snuke 了解到 Sumeko 在第 $ i $ 回合一定会出示 $ A_i $ 这张卡片。

请计算 Snuke 在每个回合中可能收到的最大伤害的最小值。
注意，每回合结束后，Sumeko 会替 Snuke 恢复他的伤害。

输入从标准输入获取，格式如下：

$ N $ $ T $ $ K $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

• 第一行包含三个整数：总回合数 $ N $（$ 1 \leq N \leq 100,000 $）、Snuke 开始持有卡片上的数 $ T $（$ 1 \leq T \leq 10^9 $），以及 Snuke 的硬币数量 $ K $（$ 1 \leq K \leq N $）。
• 第二行包含 $ N $ 个整数，第 $ i $ 个整数表示 Sumeko 在第 $ i $ 回合出示的卡片上的数 $ A_i $（$ 1 \leq A_i \leq 10^9 $）。

输出一个整数，表示 Snuke 在每个回合中的最大可能伤害的最小值，并且在一行后添加一个换行符。

部分分数

题目设有部分分。如果满足条件 $ N = K $，则解决问题可以获得 20 分。

本翻译由 AI 自动生成