Escape the Pyramid

Dr. Kong, an archaeologist, is trapped inside an ancient pyramid. The pyramid is built in levels; the i-th level has 2i-1 triangular rooms labeled as (i, j) with 1 ≤ j ≤ 2i-1. A room may have an exit. When Dr. Kong enters a room with an exit, he can leave the pyramid in 1 minute.

The rooms are connected as follows:

• For any room (i, j), you can always move horizontally to (i, j-1) (if j > 1) and (i, j+1) (if j < 2i-1).
• Vertical connections are determined by the following rules. Consider a room at level i with coordinate (i, j):
  • If j is odd (i.e. the room is considered a downward triangle) and i is not the bottom level, then it has two downward neighbors: (i+1, j) and (i+1, j+1).
  • If i > 1, then the room (i, j) is connected upward to room(s) in level i-1: specifically, for a candidate k in {j-1, j} that is within the valid range [1, 2(i-1)-1] and is odd, there is an edge from (i, j) to (i-1, k).
  These rules ensure each shared wall between two adjacent triangular rooms (neighbors) can be broken with a cost of K minutes.

If Dr. Kong travels through a sequence of moves, breaking one wall per move at a cost of K minutes per move, and then uses 1 extra minute to exit the pyramid once he reaches an exit room, the total required time is

where d is the minimum number of moves needed to reach an exit room. Given the total available time S minutes, your task is to find an exit that minimizes the time cost. If such a route is possible (i.e. the remaining time \(S - (d \times K + 1)\) is ≥ 0), output the remaining time; otherwise, output -1.

inputFormat

The first line contains three integers n, K and S (1 ≤ n ≤ 1000, K, S are positive), where n is the number of levels in the pyramid, K is the time (in minutes) to break one wall between adjacent rooms and S is the total available time.

The second line contains two integers r and c (1-indexed), representing the starting room at level r and its position c.

Then follow n lines. The i-th line is a string of length 2i-1 consisting only of the characters '0' and '1'. A character '1' indicates that room (i, j) has an exit, while '0' denotes no exit.

outputFormat

Output a single integer: if it is possible for Dr. Kong to escape the pyramid within time S, print the remaining time, i.e.

where d is the minimum number of moves. Otherwise, output -1.

sample

3 2 10
2 2
0
010
00100

9