你是一位业余天文学家！最近，你一直在研究天空中由 $n$ 颗星星组成的特定序列，并在 $n$ 个位置进行观测。每颗星星都有一个固定的亮度值，但它们的位置每天都会逆时针旋转 $k$ 个位置并循环。

例如，如果星星的原始序列在第 1 天的亮度值为 $[1, 2, 3, 4, 5]$ 且 $k = 2$，那么在第 2 天，该序列将呈现为 $[3, 4, 5, 1, 2]$。下图展示了在接下来的 $n = 5$ 天中，这些星星的呈现方式。

图 H.1：第一个样例的图示。在第 2 到 3 天期间，位置 [1, 3] 上的星星的最大亮度总和为 20。

你相信在星星最亮的日子里会发生好事。因此，你计划进行一次为期 $d$ 天的旅行，从 $s$ 个连续的位置观测星星。你希望选择合适的位置和日期，使得在这些天里这些位置上的星星亮度总和最大。换句话说，你希望在接下来的 $n$ 天中，选择任意连续的 $d$ 天，以及任意连续的 $s$ 个位置，使得星星的亮度总和最大。注意，你选择的 $s$ 个位置不能循环（即不能跨越边界折返）。

输入格式

输入的第一行包含四个整数 $n$、$k$、$d$ 和 $s$（$1 \le n \le 2 \cdot 10^5$，$0 \le k \le 10^9$，$1 \le d, s \le n$）。

接下来的 $n$ 行，每行包含一个介于 $-10^7$ 和 $10^7$ 之间（含边界）的整数。第 $i$ 行的整数表示第 $i$ 颗星星在第一天的亮度值。

输出格式

输出一个整数，表示在接下来的 $n$ 天中，任意连续 $d$ 天内任意连续 $s$ 个位置上星星的最大亮度总和。

样例

输入样例 1

5 2 2 3
1
2
3
4
5

输出样例 1

20

输入样例 2

4 2 3 2
6
-2
8
1

输出样例 2

22

输入样例 3

5 2 4 4
-1
3
-5
-7
-9

输出样例 3

-58

输入样例 4

1 1 1 1
1

输出样例 4

1