Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3741
Eternal Reality

Time Limit: 2 Seconds      Memory Limit: 65536 KB

In Academy City, most students have special abilities. Such as Railgun, Teleport, Telekinesis, AIM Stalker and so on. Here, AIM (An Involuntary Movement) is a term used to refer to the phenomenon in which an esper involuntarily produces an invisible energy field around the esper. Different students have different type of AIM dispersion field, so they also have different level of abilities.

Of course, a higher level students can often deal with more issues than a lower level students. To classify the students in Academy City, there are 7 levels in total:

Level Term Description
Level 0 Person with No Powers Most students of this level can't keep up at school. They might possess some degree of power, but unable to truly control it.
Level 1 Person with Low Powers Powers of the degree to bend a spoon, many students belong here.
Level 2 Person with Unusual Powers Just like Level 1, powers are not very useful in everyday life.
Level 3 Person with Strong Powers The degree when powers are considered convenient in everyday life, ability-wise this is the Level when one starts to be treated as part of the elite.
Level 4 Person with Great Powers Powers of an extent that their owner acquires tactical value of a military force.
Level 5 Person with Super Powers Powers of an extent that their owner can fight alone against a military force on equal terms.
Level 6 Person with Absolute Powers Powers of an extent that they're considered immeasurable. However, no one can achieve this level, even with the help of Level Upper (it has no effect on persons with super powers). Since this, many institutions have been doing long-term researches about it, such as the Radio Noise Project.

You are a student of level L in Academy City and you are going to take part in a sports competition. The competition consists of N consecutive matches. If you want to get a point in the i-th match, your must reach at least Ai level. According to the rules, you must compete in all matches one by one.

To tell the truth, it won't be easy to compete with so many high-level opponents. Fortunately, you got a special item called Level Upper. Generally, it can increase your level by 1 for a short time. If you use the Level Upper before the i-th match, it's effect will last during the matches [i, i + X - 1]. But it also has a side effect that will make your level become 0 during the matches [i + X, i + X + Y - 1]. After the side effect ends, your level will return to L and you can use the Level Upper again.

Please calculate the maximal points you can get if you properly use the Level Upper.


There are multiple test cases (plenty of small cases with several large cases). For each test case:

The first line contains four integers L (0 <= L <= 5), N, X and Y (1 <= N, X, Y <= 100). The next line contains N integers Ai (0 <= Ai <= 6).


For each test case, output the maximal points you can get.

Sample Input

3 6 1 2
1 3 4 5 6 4

Sample Output



Read the problem description carefully.

Author: JIANG, Kai
Contest: ZOJ Monthly, December 2013
Submit    Status