Some people leave the lights at their workplaces on when they leave that is a waste of resources. As a hausmeister of DHBW, Sagheer waits till all students and professors leave the university building, then goes and turns all the lights off.

The building consists of n floors with stairs at the left and the right sides. Each floor has m rooms on the same line with a corridor that connects the left and right stairs passing by all the rooms. In other words, the building can be represented as a rectangle with n rows and m + 2 columns, where the first and the last columns represent the stairs, and the m columns in the middle represent rooms.

Sagheer is standing at the ground floor at the left stairs. He wants to turn all the lights off in such a way that he will not go upstairs until all lights in the floor he is standing at are off. Of course, Sagheer must visit a room to turn the light there off. It takes one minute for Sagheer to go to the next floor using stairs or to move from the current room/stairs to a neighboring room/stairs on the same floor. It takes no time for him to switch the light off in the room he is currently standing in. Help Sagheer find the minimum total time to turn off all the lights.

Note that Sagheer does not have to go back to his starting position, and he does not have to visit rooms where the light is already switched off.

Input

The first line contains two integers n and m (1 ≤ n ≤ 15 and 1 ≤ m ≤ 100) — the number of floors and the number of rooms in each floor, respectively.

The next n lines contains the building description. Each line contains a binary string of length m + 2 representing a floor (the left stairs, then m rooms, then the right stairs) where 0 indicates that the light is off and 1 indicates that the light is on. The floors are listed from top to bottom, so that the last line represents the ground floor.

The first and last characters of each string represent the left and the right stairs, respectively, so they are always 0.

Output

Print a single integer — the minimum total time needed to turn off all the lights.

Examples

Input

2 2
0010
0100


Output

5


Input

3 4
001000
000010
000010


Output

12


Input

4 3
01110
01110
01110
01110


Output

18

Note

In the first example, Sagheer will go to room 1 in the ground floor, then he will go to room 2 in the second floor using the left or right stairs.

In the second example, he will go to the fourth room in the ground floor, use right stairs, go to the fourth room in the second floor, use right stairs again, then go to the second room in the last floor.

In the third example, he will walk through the whole corridor alternating between the left and right stairs at each floor.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Iterator;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.NoSuchElementException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Nguyen Trung Hieu - vuondenthanhcong11@gmail.com
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskB solver = new TaskB();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskB {
        private int answer = Integer.MAX_VALUE;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int rowCount = in.readInt();
            int columnCount = in.readInt() + 2;
            char[][] table = IOUtils.readTable(in, rowCount, columnCount);

            int total = 0;
            for (int i = 0; i < rowCount; i++) {
                total += ArrayUtils.count(table[i], '1');
            }

            if (total == 0) {
                out.printLine(0);
                return;
            }

            int[] firstOne = new int[rowCount];
            int[] lastOne = new int[rowCount];
            int[] exist = new int[rowCount];

            Arrays.fill(firstOne, -1);
            Arrays.fill(lastOne, -1);

            for (int i = 0; i < rowCount; i++) {
                for (int j = 0; j < columnCount; j++) {
                    if (table[i][j] == '1') {
                        if (firstOne[i] < 0) {
                            firstOne[i] = j;
                        }
                        lastOne[i] = j;
                        exist[i]++;
                    }
                }
            }

            answer = Integer.MAX_VALUE;
            dfs(rowCount - 1, 0, 0, 'l', total, firstOne, lastOne, exist, rowCount, columnCount);

            out.printLine(answer);
        }

        private void dfs(int row, int curAnswer, int curTotal, char start, int total, int[] firstOne, int[] lastOne, int[] exist, int rowCount, int columnCount) {
            if (row < 0) {
                return;
            }

            if (exist[row] == 0) {
                dfs(row - 1, curAnswer + 1, curTotal, start, total, firstOne, lastOne, exist, rowCount, columnCount);
                dfs(row - 1, curAnswer + columnCount, curTotal, start == 'l' ? 'r' : 'l', total, firstOne, lastOne, exist, rowCount, columnCount);
            } else if (start == 'l') {
                curAnswer += lastOne[row];
                curTotal += exist[row];
                if (curTotal == total) {
                    answer = Math.min(answer, curAnswer);
                    return;
                }

                // end right
                dfs(row - 1, curAnswer + 1 + (columnCount - 1 - lastOne[row]), curTotal, 'r', total, firstOne, lastOne, exist, rowCount, columnCount);

                // end left;
                dfs(row - 1, curAnswer + 1 + lastOne[row], curTotal, 'l', total, firstOne, lastOne, exist, rowCount, columnCount);
            } else if (start == 'r') {
                curAnswer += (columnCount - 1 - firstOne[row]);
                curTotal += exist[row];
                if (curTotal == total) {
                    answer = Math.min(answer, curAnswer);
                    return;
                }

                // end right
                dfs(row - 1, curAnswer + 1 + (columnCount - 1 - firstOne[row]), curTotal, 'r', total, firstOne, lastOne, exist, rowCount, columnCount);

                // end left
                dfs(row - 1, curAnswer + 1 + firstOne[row], curTotal, 'l', total, firstOne, lastOne, exist, rowCount, columnCount);
            }
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public char readCharacter() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            return (char) c;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static class ArrayUtils {
        public static int count(char[] array, char value) {
            return new CharArray(array).count(value);
        }

    }

    static interface CharStream extends Iterable<Character>, Comparable<CharStream> {
        public CharIterator charIterator();

        default public Iterator<Character> iterator() {
            return new Iterator<Character>() {
                private CharIterator it = charIterator();

                public boolean hasNext() {
                    return it.isValid();
                }

                public Character next() {
                    char result = it.value();
                    it.advance();
                    return result;
                }
            };
        }

        default public int compareTo(CharStream c) {
            CharIterator it = charIterator();
            CharIterator jt = c.charIterator();
            while (it.isValid() && jt.isValid()) {
                char i = it.value();
                char j = jt.value();
                if (i < j) {
                    return -1;
                } else if (i > j) {
                    return 1;
                }
                it.advance();
                jt.advance();
            }
            if (it.isValid()) {
                return 1;
            }
            if (jt.isValid()) {
                return -1;
            }
            return 0;
        }

        default public int count(char value) {
            int result = 0;
            for (CharIterator it = charIterator(); it.isValid(); it.advance()) {
                if (it.value() == value) {
                    result++;
                }
            }
            return result;
        }

    }

    static class CharArray extends CharAbstractStream implements CharList {
        private char[] data;

        public CharArray(char[] arr) {
            data = arr;
        }

        public int size() {
            return data.length;
        }

        public char get(int at) {
            return data[at];
        }

        public void removeAt(int index) {
            throw new UnsupportedOperationException();
        }

    }

    static interface CharIterator {
        public char value() throws NoSuchElementException;

        public boolean advance();

        public boolean isValid();

    }

    static interface CharCollection extends CharStream {
        public int size();

    }

    static abstract class CharAbstractStream implements CharStream {

        public String toString() {
            StringBuilder builder = new StringBuilder();
            boolean first = true;
            for (CharIterator it = charIterator(); it.isValid(); it.advance()) {
                if (first) {
                    first = false;
                } else {
                    builder.append(' ');
                }
                builder.append(it.value());
            }
            return builder.toString();
        }


        public boolean equals(Object o) {
            if (!(o instanceof CharStream)) {
                return false;
            }
            CharStream c = (CharStream) o;
            CharIterator it = charIterator();
            CharIterator jt = c.charIterator();
            while (it.isValid() && jt.isValid()) {
                if (it.value() != jt.value()) {
                    return false;
                }
                it.advance();
                jt.advance();
            }
            return !it.isValid() && !jt.isValid();
        }


        public int hashCode() {
            int result = 0;
            for (CharIterator it = charIterator(); it.isValid(); it.advance()) {
                result *= 31;
                result += it.value();
            }
            return result;
        }

    }

    static class IOUtils {
        public static char[] readCharArray(InputReader in, int size) {
            char[] array = new char[size];
            for (int i = 0; i < size; i++) {
                array[i] = in.readCharacter();
            }
            return array;
        }

        public static char[][] readTable(InputReader in, int rowCount, int columnCount) {
            char[][] table = new char[rowCount][];
            for (int i = 0; i < rowCount; i++) {
                table[i] = readCharArray(in, columnCount);
            }
            return table;
        }

    }

    static interface CharList extends CharReversableCollection {
        public abstract char get(int index);

        public abstract void removeAt(int index);

        default public CharIterator charIterator() {
            return new CharIterator() {
                private int at;
                private boolean removed;

                public char value() {
                    if (removed) {
                        throw new IllegalStateException();
                    }
                    return get(at);
                }

                public boolean advance() {
                    at++;
                    removed = false;
                    return isValid();
                }

                public boolean isValid() {
                    return !removed && at < size();
                }

                public void remove() {
                    removeAt(at);
                    at--;
                    removed = true;
                }
            };
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void printLine(int i) {
            writer.println(i);
        }

    }

    static interface CharReversableCollection extends CharCollection {
    }
}

