D.序列(array)

时间限制：3s

空间限制：512MB

题意

给定一个长度为 $n$ 的整数序列 $a_1,a_2,..,a_n$，同时给定另外四个整数 $k,m,c,d$。

小 L 可以进行以下操作至多一次：选择一个长度恰为 $m$ 的连续子数组，并将一个长度为 $m$ ，首项为 $c$ ，公差为 $d$ 的等差数列加到该连续子数组上。

如序列是 $3,1,4,1,5$，将一个长度为 $m=3$，首项为 $c=2$，公差为 $d=1$ 的等差子序列，加到序列中 $a_2,a_3,a_4$ 这个长度为 $3$ 的连续子数组上，则序列变成 $3,3,7,5,5$。

小 L 希望最大化序列中第 $k$ 大的值。

输入格式

第一行输入五个整数 $n,k,m,c,d$ ，含义如题目所示。

第二行输入 $n$ 个数，第 $i$ 个数为 $a_i$ 。

输出格式

一行一个整数，表示序列中第 $k$ 大的值的最大值。

样例1

输入

8 3 5 0 0
2 0 2 2 1 2 1 8

输出

2

数据范围

对于 $20\%$ 的数据，保证 $1\le k,m\le n\le 10$。

对于另外 $20\%$ 的数据，保证 $1\le k,m\le n\le 1000$。

对于另外 $30\%$ 的数据，保证 $k=1$。

对于 $100\%$ 的数据，保证 $1\le k,m\le n\le 2\times 10^5,0\le c,d\le 10^9,0\le a_i\le 10^9$。