Limits 1s, 512 MB

Every kid loves to play Super Mario Bros. Mario moveু forward and collects coins in a stage. Stages are built with traps, hills, etc and has some coins with points. Mario can jump to avoid traps and/or collect coins. He can collect coins just by touching it and get points written in the coins.

You are playing this game now. You want to maximize points even if you don't finish this level. You want to know how many points you may score. You just started this game so you are in level-1. In this level, there will be no hills but may contain traps. Mario can walk from any cell ii to the next cell i+1i+1. And all coins lay on the floor. That means you can collect coin if you go to the cell and if you jump over the cell you can't get that coin. When you jump from the ii-th cell you will end up in i+ki+k-th cell and you will not get any point from cell i+1i+1-th to i+k1i+k-1-th cell. If you end up in a trap by jumping/waking you will be dead. You don’t want to walk for too long. You want to walk at most ww consecutive cells. Suppose you started walking from the ii-th cell and you will jump at least once between the ii-th cell and i+w1i+w-1-th cell. You start at cell 11. Cell 1 will never have a trap.

You have to find the maximum points you get.

Input

In the first line, their will be one string to represent the game layout. '*' denote traps and '1'-'9' denote the point of the coin in that cell. '0' means empty cell. The length of the string will be at most 10610^6. In the next line there will be 2 integers kk (k1k≥1), ww (w1w≥1).

Output

Print an integer in one line denoting the answer.

Samples

InputOutput
10122030
2 2
8
InputOutput
1*122030
2 2
7
InputOutput
014*022030**9
2 3
12

Submit

Login to submit.

Statistics

62% Solution Ratio
rebornEarliest, Sep '19
nusuBotFastest, 0.0s
ioi_comradesLightest, 13 MB
CoderMShortest, 587B
Toph uses cookies. By continuing you agree to our Cookie Policy.