You're the researcher of the International Chat Program Company (ICPC). Today, you discover the following chat history when reviewing some research data.
SUA (2022/12/04 23:01:25)
I'm out of ideas for competitive programming problems! Please give me a problem about sequences.
BOT (2022/12/04 23:01:27)
Sure. Here is a competitive programming problem about sequences.
Given an integer sequence $$$a_1, a_2, \cdots, a_n$$$ of length $$$n$$$ and four other integers $$$k$$$, $$$m$$$, $$$c$$$ and $$$d$$$, your goal is to maximize the $$$k$$$-th largest element in the sequence.
To achieve the goal, you can perform the following operation at most once: select a continuous sub-array of length $$$m$$$ and add an arithmetic sequence with length $$$m$$$, initial term $$$c$$$ and common difference $$$d$$$ to the sub-array.
More formally, you can select an integer $$$p$$$ satisfying $$$1 \le p \le n - m + 1$$$ and add $$$(c + di)$$$ to $$$a_{p + i}$$$ for all $$$0 \le i < m$$$.
Calculate the largest possible value of the $$$k$$$-th largest element in the sequence after at most one operation.
The $$$k$$$-th largest element in the sequence is the $$$k$$$-th element in the sorted sequence after sorting all elements from the largest to the smallest. For example, the $$$3$$$rd largest element in sequence $$$\{5, 7, 1, 9\}$$$ is $$$5$$$, while the $$$3$$$rd largest element in sequence $$$\{9, 7, 5, 9\}$$$ is $$$7$$$.
SUA (2022/12/05 00:15:17)
This problem seems difficult! Please teach me the solution.
BOT (2022/12/05 00:15:30)
Sure. Firstly, we can...
[DATA EXPUNGED]
Unfortunately, parts of the chat history are lost due to a disk failure. You're amazed at how a chat program can create a competitive programming problem. To verify whether the chat program can create valid problems, you decide to try on this problem.
There is only one test case in each test file.
The first line contains five integers $$$n$$$, $$$k$$$, $$$m$$$, $$$c$$$ and $$$d$$$ ($$$1 \le k, m \le n \le 2 \times 10^5$$$, $$$0 \le c, d \le 10^9$$$) indicating the length of the sequence, your goal, the length, initial term and common difference of the arithmetic sequence.
The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) indicating the sequence.
Output one line containing one integer indicating the largest possible value of the $$$k$$$-th largest element in the sequence after at most one operation.
6 4 3 1 2 1 1 4 5 1 4
4
7 3 2 4 0 1 9 1 9 8 1 0
9
8 3 5 0 0 2 0 2 2 1 2 1 8
2
For the first sample test case, we can choose $$$p = 3$$$ so the sequence becomes $$$\{1, 1, 5, 8, 6, 4\}$$$. The $$$4$$$-th largest element in the sequence is $$$4$$$.
For the second sample test case, we can choose $$$p = 5$$$ so the sequence becomes $$$\{1, 9, 1, 9, 12, 5, 0\}$$$. The $$$3$$$-rd largest element in the sequence is $$$9$$$.
For the third sample test case, it is easy to see that the operation does not change the sequence, so we choose not to perform the operation. The $$$3$$$-rd largest element in the sequence is $$$2$$$.
OpenAI ChatGPT is encouraging the contestants
