Raon and Candy

Raon is enjoying her long weekend by playing her favorite video game, "Give Me My Candy!!", an addictive single player puzzle game. In each level, the player will be given the layout of a building. The building has N floors, each floor has M rooms, and each room has some candies in it. On each floor, there are two stairs in which the player can use them to go to the next upper floor (they can't be used to go to a lower floor); one stair is located to the left of the left-most room, while the other stair is located to the right of the right-most room.

The player starts from the lowest floor (1st floor) at the left stair. It takes one second for the player to either move to adjacent room/stair (if she's at a room/stair) or to go to the next upper floor (if she's at a stair). It takes NO time to collect the candies in a room where the player is. The objective is to reach the highest floor's stair (either stairs) while collecting at least C candies along the way. Of course, she has to do it as fast as possible.

Given the building layout and an integer C, determine the minimum required time (in seconds) to achieve the goal.

Input

Input begins with three integers: N M C (1 ≤ N, M ≤ 100; 1 ≤ C ≤ 1,000) denoting the number of floors, rooms in each floor, and minimum collected candies, respectively. The next N lines describe the building layout from the highest to the lowest floor (i.e. the last line of the layout is the 1st floor). Each line contains M + 2 characters representing two stairs and the rooms in that particular floor. The stairs are located at the left-most and right-most of each line and are represented by character '|' (vertical bar). The M characters in between represents the number of candies in each room, which are between 0 and 9, inclusive. You may safely assume that C is no more than the total number of available candies.

Output

Output in a line an integer representing the output for the given input.

Examples

inputExample #1
3 4 7
|4010|
|0002|
|0020|
output
12
explanation
  • 1st floor, left stair: collect all 2 candies in this floor, move to the right stair, and go to the 2nd floor → 6 second.
  • 2nd floor, right stair: go to the 3rd floor → 1 seconds.
  • 3rd floor, right stair: collect all 5 candies in this floor, move to the left stair → 5 seconds.
The player managed to collect 2 + 5 = 7 candies and end up at the left stair in the highest floor. The total time: 6 + 1 + 5 = 12 seconds.

inputExample #2
4 5 8
|02001|
|40020|
|01000|
|00020|
output
15
explanation
  • 1st floor, left stair: go to the 2nd floor → 1 second.
  • 2nd floor, left stair: collect 1 candy in the second room, move back to the left stair, and go to the 3rd floor → 5 seconds.
  • 3rd floor, left stair: collect all 6 candies in this floor, move to the right stair, and go to the 4th floor → 7 seconds.
  • 4th floor, right stair: collect 1 candy in the fifth room, move back to the right stair → 2 seconds.
The player managed to collect 1 + 6 + 1 = 8 candies and end up at the right stair in the highest floor. The total time: 1 + 5 + 7 + 2 = 15 seconds.

inputExample #3
4 4 5
|0200|
|8000|
|0100|
|0020|
output
5
explanation
  • 1st floor, left stair: go to the 2nd floor → 1 second.
  • 2nd floor, left stair: go to the 3rd floor → 1 second.
  • 3rd floor, left stair: collect 1 candy in the first room, move back to the left stair, and go to the 4th floor → 3 seconds.
  • 4th floor, right stair: stay → 0 second.
The player managed to collect 8 candies and end up at the left stair in the highest floor. The total time: 1 + 1 + 3 = 5 seconds.


End of Problem