Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Super Mario Bros

By kazi_nayeem · 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 i to the next cell (i+1). nd 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 i-th cell you will end up in (i+k)-th cell and you will not get any point from cell (i+1)-th to (i+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 w consecutive cells. Suppose you started walking from thei-th cell and you will jump at least once between the i-th cell and (i+w-1)-th cell. You start at cell 1. 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 106. In the next line there will be 2 integers k(k≥1), w(w≥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

Discussion

Statistics


61% Solution Ratio

rebornEarliest, Sep '19

YouKnowWhoFastest, 0.0s

ioi_comradesLightest, 13 MB

CoderMShortest, 587B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.