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 to the next cell . 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 -th cell you will end up in -th cell and you will not get any point from cell -th to -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 consecutive cells. Suppose you started walking from the -th cell and you will jump at least once between the -th cell and -th cell. You start at cell . Cell 1 will never have a trap.
You have to find the maximum points you get.
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 . In the next line there will be 2 integers (), ().
Print an integer in one line denoting the answer.
Input | Output |
---|---|
10122030 2 2 | 8 |
Input | Output |
---|---|
1*122030 2 2 | 7 |
Input | Output |
---|---|
014*022030**9 2 3 | 12 |