You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

众所周知，埃隆·马斯克是世界首富，不仅创办了特斯拉、脑机接口公司，而且还将众多富豪送入了火星，不仅科技成果显著，而且他还是一位音乐爱好者。

他没日没夜的创作音乐，追求完美的五音符序列。最近，他得到了一个长度为 $n$ 的五音符序列 $a_1,a_2,..,a_n$。

马克思发现了一种神奇的音符变奏技巧，这种技巧需要三个参数：$m$、$c$、$d$。通过这项技巧，他可以在原始音符序列中选择一个长度为 $m$ 的连续子序列，并将一个长度为 $m$、首个音符为 $c$、音程差为 $d$ 的等差音符序列添加到该连续子序列上。马斯克可以运用这种变奏技巧至多一次。

例如，如果原始音符序列是 $3,1,4,1,5$，小明将一个长度为 $m=3$，首项为 $c=2$，公差为 $d=1$ 的等差音符序列 $2,3,4$ 叠加到序列中 $a_2,a_3,a_4$ 这个连续子音符序列上，叠加后的音符序列变为 $3,3,7,5,5$。

马斯克认为，一组音符序列中第 $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

样例输出 1

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$。