P14156 [ICPC 2022 Nanjing R] 聊天程序

您是国际聊天程序公司（International Chatting Program Company，ICPC）的研究员。今天，您在浏览研究数据时，发现了以下聊天记录。 $\textbf{SUA（2022/12/04 23:01:25）}$ 我已经用光了程序设计竞赛题目的点子！请给我一道关于序列的题目。 $\textbf{机器人（2022/12/04 23:01:27）}$ 当然可以，下面是一道关于序列的程序设计竞赛的题目。 给定一个长度为 $n$ 的整数序列 $a_1, a_2, \cdots, a_n$，同时给定另外四个整数 $k$，$m$，$c$ 与 $d$，您的目标是最大化序列中第 $k$ 大的值。 为了达成这一目标，您可以进行以下操作至多一次：选择一个长度恰为 $m$ 的连续子数组，并将一个长度为 $m$，首项为 $c$，公差为 $d$ 的等差序列加到该连续子数组上。 更正式地，您可以选择一个整数 $p$ 满足 $1 \le p \le n - m + 1$，并对于所有 $0 \le i < m$，将 $a_{p + i}$ 增加 $(c + di)$。 求至多一次操作之后，序列中第 $k$ 大的值最大可能是多少。 序列中第 $k$ 大的值，指的是将序列从大到小排序后，位于序列第 $k$ 项的值。例如，序列 $\{5, 7, 1, 9\}$ 中，第 $3$ 大的值为 $5$；而序列 $\{9, 7, 5, 9\}$ 中，第 $3$ 大的值为 $7$。 $\textbf{SUA（2022/12/05 00:15:17）}$ 这道题目好像很难！请告诉我它的解法。 $\textbf{机器人（2022/12/05 00:15:30）}$ 当然可以。首先，我们可以... [数据删除] 遗憾的是，部分聊天记录由于硬盘损坏而丢失了。您为聊天程序可以创造程序设计竞赛的题目而感到非常惊奇。为了验证聊天程序是否能创造有效的题目，您决定尝试解决这道题目。

每个测试文件仅有一组测试数据。 第一行输入五个整数 $n$，$k$，$m$，$c$ 和 $d$（$1 \le k, m \le n \le 2 \times 10^5$，$0 \le c, d \le 10^9$）表示序列的长度，您的目标，等差序列的长度，首项和公差。 第二行输入 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$0 \le a_i \le 10^9$）表示给定的序列。

输出一行一个整数，表示至多一次操作之后，序列中第 $k$ 大的值最大可能是多少。

对于第一组样例数据，可以选择 $p = 3$ 使序列变为 $\{1, 1, 5, 8, 6, 4\}$。序列中第 $4$ 大的值为 $4$。 对于第二组样例数据，可以选择 $p = 5$ 使序列变为 $\{1, 9, 1, 9, 12, 5, 0\}$。序列中第 $3$ 大的值为 $9$。 对于第三组样例数据，容易发现操作不改变序列的值，因此我们选择不进行操作。序列中第 $3$ 大的值为 $2$。 :::align{center}  OpenAI ChatGPT 正在鼓励选手 :::