ZOJ Problem Set - 3741
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:
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.
3 6 1 2 1 3 4 5 6 4
Read the problem description carefully.
Author: JIANG, Kai
Contest: ZOJ Monthly, December 2013