该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

小 $G$ 可以进行以下操作至多一次：选择一个长度恰为 $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$。

小 $G$ 希望最大化序列中第 $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

输入样例2

10 4 4 5 0
1 14 51 4 19 19 8 10 0 10

输出样例2

19

大样例详见 sequence.in, sequence.out

数据范围

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

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

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

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