题目描述

你正在观察天空中一排 $n$ 颗星星。每颗星星有固定亮度值，但每天它们的位置都会逆时针旋转 $k$ 个位置并循环。

例如，第一天亮度序列为 $[1,2,3,4,5]$，且 $k=2$，则第二天看到的序列为 $[3,4,5,1,2]$。

你准备进行一次持续 $d$ 天的观测旅行，并选择连续的 $s$ 个观测点。你希望选择连续的 $d$ 天和连续的 $s$ 个位置，使这 $d\times s$ 个观测值的亮度总和最大。

需要注意，选择的 $s$ 个位置不能跨过边界，即不能在一行内环绕。

只考虑接下来的 $n$ 天。

输入格式

第一行包含四个整数 $n,k,d,s$：

$$1\le n\le 2\cdot 10^5, \qquad 0\le k\le 10^9, \qquad 1\le d,s\le n.$$

接下来 $n$ 行，每行一个整数，表示第一天第 $i$ 颗星的亮度，范围为 $[-10^7,10^7]$。

输出格式

输出一个整数，表示任意连续 $d$ 天、任意连续 $s$ 个位置的最大亮度总和。

样例 #1

输入

5 2 2 3
1
2
3
4
5

输出

20

样例 #2

输入

4 2 3 2
6
-2
8
1

输出

22

样例 #3

输入

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

输出

-58

样例 #4

输入

1 1 1 1
1

输出

1