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.
#include <bits/stdc++.h>
using namespace std;
const int dr[4] = {0, 0, -1, 1}, dc[4] = {-1, 1, 0, 0};
class Dijkstra {
  int N;
  vector<vector<pair<int, int> > > E;

 public:
  Dijkstra(int n) {
    N = n;
    E = vector<vector<pair<int, int> > >(N + 1);
  }
  void insert(int u, int v, int w) { E[u].push_back(make_pair(v, w)); }
  vector<int> dijkstra(int start, int end) {
    vector<int> dist(N + 1, 1000000007);
    dist[start] = 0;
    priority_queue<pair<int, int> > pq;
    pq.push(make_pair(0, start));
    while (!pq.empty()) {
      int w = -pq.top().first;
      int u = pq.top().second;
      if (u == end) return dist;
      pq.pop();
      if (dist[u] < w) continue;
      for (int i = 0; i < E[u].size(); i++) {
        int v = E[u][i].first;
        int w2 = w + E[u][i].second;
        if (dist[v] > w2) {
          dist[v] = w2;
          pq.push(make_pair(-w2, v));
        }
      }
    }
    return dist;
  }
  void g() {
    int i, n, e, s, u, v, w;
    vector<int> ans;
    scanf("%d%d", &n, &e);
    Dijkstra dk(n);
    scanf("%d", &s);
    for (i = 0; i < e; i++) {
      scanf("%d%d%d", &u, &v, &w);
      dk.insert(u, v, w);
    }
    ans = dk.dijkstra(s, N);
    for (i = 1; i <= n; i++) {
      if (ans[i] >= 1000000007)
        printf("INF\n");
      else
        printf("%d\n", ans[i]);
    }
  }
};
class Prim {
  int N;
  vector<vector<pair<int, int> > > E;

 public:
  Prim(int n) {
    N = n;
    E = vector<vector<pair<int, int> > >(N + 1);
  }
  void insert(int u, int v, int w) { E[u].push_back(make_pair(v, w)); }
  vector<int> execute(long long &cost) {
    int k;
    vector<int> dist(N + 1, 1000000007);
    vector<bool> selected(N + 1, false);
    dist[1] = 0;
    cost = 0;
    priority_queue<pair<int, int> > pq;
    pq.push(make_pair(0, 1));
    for (k = 0; k < N; k++) {
      int w = -pq.top().first;
      int u = pq.top().second;
      pq.pop();
      if (selected[u] == true) {
        k--;
        continue;
      }
      cost += w;
      selected[u] = true;
      for (int i = 0; i < E[u].size(); i++) {
        int v = E[u][i].first;
        int w2 = E[u][i].second;
        if (selected[v] == true) continue;
        if (dist[v] > w2) {
          dist[v] = w2;
          pq.push(make_pair(-w2, v));
        }
      }
    }
    return dist;
  }
  void g() {
    int i, n, e, s, u, v, w;
    long long cost;
    vector<int> ans;
    scanf("%d%d", &n, &e);
    Prim pm(n);
    scanf("%d", &s);
    for (i = 0; i < e; i++) {
      scanf("%d%d%d", &u, &v, &w);
      pm.insert(u, v, w);
    }
    ans = pm.execute(cost);
    printf("%d", cost);
  }
};
class Floyd {
  int N;
  vector<vector<int> > E;

 public:
  Floyd(int n) {
    N = n;
    E = vector<vector<int> >(N + 1, vector<int>(N + 1, 1000000007));
  }
  void setRC(int r, int c, int w) { E[r][c] = w; }
  int getRC(int r, int c) { return E[r][c]; }
  void execute() {
    int i, j, k;
    for (i = 1; i <= N; ++i) E[i][i] = 0;
    for (k = 1; k <= N; ++k)
      for (i = 1; i <= N; ++i)
        for (j = 1; j <= N; ++j) E[i][j] = min(E[i][j], E[i][k] + E[k][j]);
  }
};
class DFS_Graph {
  vector<vector<pair<int, int> > > E;
  vector<int> A;
  int N;

 public:
  DFS_Graph(int n) {
    N = n;
    E = vector<vector<pair<int, int> > >(N + 1);
    A = vector<int>(N + 1);
  }
  void insert(int u, int v, int w) { E[u].push_back(make_pair(v, w)); }
  void insert_fb(int u, int v, int w) {
    E[u].push_back(make_pair(v, w));
    E[v].push_back(make_pair(u, w));
  }
  int dfsAll(int start, int end) {
    vector<bool> visited = vector<bool>(N + 1, false);
    return dfs(start, end, visited);
  }
  int dfs(int start, int end, vector<bool> &visited) {
    if (start == end) return 1;
    visited[start] = true;
    for (int i = 0; i < E[start].size(); i++) {
      int v = E[start][i].first, c = E[start][i].second;
      if (!visited[v]) {
        if (dfs(v, end, visited)) return 1;
      }
    }
    return 0;
  }
  void setA(int a, int b) { A[a] = b; }
  int dfsAll2() {
    vector<int> visited(N + 1, 0);
    int i, j, seq = 0, ret = 0, a;
    for (i = 1; i <= N; i++) dfs2(i, visited, ++seq);
    for (i = 1; i <= N; i++) {
      for (j = a = 0; j < E[i].size(); j++) {
        a += E[i][j].second;
      }
      if (ret < a) ret = a;
    }
    return ret;
  }
  int dfs2(int start, vector<int> &visited, long long seq) {
    visited[start] = seq;
    int ret = A[start];
    for (int i = 0; i < E[start].size(); i++) {
      int v = E[start][i].first;
      long long c = E[start][i].second;
      if (visited[v] < seq) {
        if (E[start][i].second == -1)
          E[start][i].second = dfs2(v, visited, seq);
        if (ret < E[start][i].second) ret = E[start][i].second;
      }
    }
    return ret;
  }
  void g() {
    int i, j, N, m, a, b, c, a2, b2, c2, lo, hi, mid, tmp, start, end;
    scanf("%d%d", &N, &m);
    DFS_Graph dg(N);
    for (i = 0; i < m; i++) {
      scanf("%d%d", &a, &b);
      dg.insert(a, b, 0);
    }
    scanf("%d", &m);
    for (i = 0; i < m; i++) {
      scanf("%d%d", &a, &b);
      if (dg.dfsAll(a, b))
        c = -1;
      else if (dg.dfsAll(b, a))
        c = 1;
      else
        c = 0;
      printf("%d\n", c);
    }
  }
};
class DFS_Map {
  vector<vector<int> > E;
  int R, C;

 public:
  DFS_Map(int r, int c) {
    R = r;
    C = c;
    E = vector<vector<int> >(R + 2, vector<int>(C + 2, 0));
  }
  void setRC(int r, int c, int w) { E[r][c] = w; }
  int getRC(int r, int c) { return E[r][c]; }
  void dfs(int rr, int cc, vector<vector<bool> > &visited) {
    int i, r, c, v;
    visited[rr][cc] = true;
    for (i = 0; i < 4; i++) {
      r = rr + dr[i];
      c = cc + dc[i];
      if (E[r][c] && !visited[r][c]) {
        dfs(r, c, visited);
      }
    }
  }
  void dfsAll() {
    vector<vector<bool> > visited =
        vector<vector<bool> >(R + 2, vector<bool>(C + 2, 0));
    int r, c;
    for (r = 1; r <= R; r++)
      for (c = 1; c <= C; c++)
        if (!visited[r][c]) dfs(r, c, visited);
  }
};
class BFS_Graph {
  vector<vector<pair<int, int> > > E;
  vector<int> IN;
  int N;

 public:
  int is_cycle() {
    for (int i = 1; i <= N; i++)
      if (IN[i] > 0) return 1;
    return 0;
  }
  BFS_Graph(int n) {
    N = n;
    E.clear();
    IN.clear();
    E = vector<vector<pair<int, int> > >(N + 1);
    IN = vector<int>(N + 1, 0);
  }
  void insert(int u, int v, int w) {
    E[u].push_back(make_pair(v, w));
    IN[v]++;
  }
  void insert_fb(int u, int v, int w) {
    E[u].push_back(make_pair(v, w));
    E[v].push_back(make_pair(u, w));
  }
  vector<long long> bfs(int start, int end, int min_weight) {
    vector<bool> visited = vector<bool>(N + 1, false);
    vector<long long> weight(N + 1, 1000000000000007);
    queue<int> Q;
    visited[start] = true;
    weight[start] = 0;
    Q.push(start);
    while (!Q.empty()) {
      int u = Q.front(), w = weight[u];
      if (u == end) break;
      Q.pop();
      for (int i = 0; i < E[u].size(); i++) {
        int v = E[u][i].first, c = E[u][i].second;
        if (c >= min_weight && !visited[v]) {
          Q.push(v);
          weight[v] = w + c;
          visited[v] = true;
        }
      }
    }
    return weight;
  }
  vector<int> topologicalSort() {
    vector<int> order;
    queue<int> Q;
    for (int i = 1; i <= N; i++)
      if (!IN[i]) Q.push(i);
    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();
      order.push_back(u);
      for (int i = 0; i < E[u].size(); i++) {
        int v = E[u][i].first;
        if (IN[v] > 0) {
          IN[v]--;
          if (!IN[v]) Q.push(v);
        }
      }
    }
    return order;
  }
  vector<int> topologicalSortPQ() {
    vector<int> order;
    priority_queue<int> pq;
    for (int i = 1; i <= N; i++)
      if (!IN[i]) pq.push(-i);
    while (!pq.empty()) {
      int u = -pq.top();
      pq.pop();
      order.push_back(-u);
      for (int i = 0; i < E[u].size(); i++) {
        int v = E[u][i].first;
        if (IN[v] > 0) {
          IN[v]--;
          if (!IN[v]) pq.push(-v);
        }
      }
    }
    return order;
  }
  int f() {
    int v, u, i;
    vector<int> IN2;
    for (u = 1; u <= N; u++) {
      for (i = 0; i < E[u].size(); i++) {
        v = E[u][i].first;
        if (IN[v] == 1) {
          IN2 = IN;
          IN[v]--;
          topologicalSort();
          if (!is_cycle()) return 1;
          IN = IN2;
        }
      }
    }
    return 0;
  }
  void g() {
    int i, j, N, m, a, b, c, a2, b2, c2, lo, hi, mid, tmp, start, end;
    vector<tuple<int, int, int> > X;
    vector<long long> y;
    scanf("%d%d", &N, &m);
    BFS_Graph bg(N);
    X.reserve(m);
    for (i = 0; i < m; i++) {
      scanf("%d%d%d", &a, &b, &c);
      if (a > b) tmp = a, a = b, b = tmp;
      X.push_back(make_tuple(a, b, -c));
    }
    scanf("%d%d", &start, &end);
    sort(X.begin(), X.end());
    bg.insert_fb(get<0>(X[0]), get<1>(X[0]), -get<2>(X[0]));
    for (i = 1; i < m; i++) {
      a = get<0>(X[i - 1]);
      b = get<1>(X[i - 1]);
      c = get<2>(X[i - 1]);
      a2 = get<0>(X[i]);
      b2 = get<1>(X[i]);
      c2 = get<2>(X[i]);
      if (a == a2 && b == b2) continue;
      bg.insert_fb(a2, b2, -c2);
    }
    lo = 1;
    hi = 1000000007;
    while (lo < hi) {
      mid = (lo + hi + 1) / 2;
      y = bg.bfs(start, end, mid);
      if (y[end] < 1000000000000007) {
        lo = mid;
      } else {
        hi = mid - 1;
      }
    }
    printf("%d", lo);
  }
};
class BFSMap {
  vector<vector<int> > E;
  int R, C;

 public:
  BFSMap(int r, int c) {
    R = r;
    C = c;
    E = vector<vector<int> >(R + 2, vector<int>(C + 2, 0));
  }
  void setRC(int r, int c, int w) { E[r][c] = w; }
  int getRC(int r, int c) { return E[r][c]; }
  int bfsAll() {
    int r, c, ret = 0;
    vector<vector<int> > visited =
        vector<vector<int> >(R + 2, vector<int>(C + 2, 0));
    for (r = 1; r <= R; r++) {
      for (c = 1; c <= C; c++) {
        if (E[r][c] && !visited[r][c]) {
          ret++;
          bfs(r, c, visited);
        }
      }
    }
    return ret;
  }
  int bfsAll(vector<pair<int, int> > &Q) {
    int i, r, c, ret = 0;
    vector<vector<int> > visited =
        vector<vector<int> >(R + 2, vector<int>(C + 2, 0));
    for (i = 0; i < Q.size(); i++) {
      r = Q[i].first;
      c = Q[i].second;
      if (!visited[r][c]) {
        ret++;
        bfs(r, c, visited);
      }
    }
    return ret;
  }
  void bfs(int rr, int cc, vector<vector<int> > &visited) {
    int i, r, c, r2, c2;
    queue<pair<int, int> > Q;
    Q.push(make_pair(rr, cc));
    visited[rr][cc] = 1;
    while (!Q.empty()) {
      r = Q.front().first;
      c = Q.front().second;
      Q.pop();
      for (i = 0; i < 4; i++) {
        r2 = r + dr[i];
        c2 = c + dc[i];
        if (E[r2][c2] && !visited[r2][c2]) {
          Q.push(make_pair(r2, c2));
          visited[r2][c2] = visited[r][c] + 1;
        }
      }
    }
  }
  void g() {
    int i, j, r, c, r2, c2, R, C, a, ans = 0, idx = 0;
    vector<pair<int, int> > Q[2];
    vector<int> X;
    scanf("%d%d", &R, &C);
    BFSMap bm(R, C);
    X.reserve(10004);
    Q[0].reserve(10004);
    Q[1].reserve(10004);
    for (r = 1; r <= R; r++)
      for (c = 1; c <= C; c++) {
        scanf("%d", &a);
        bm.setRC(r, c, a);
        if (a) Q[0].push_back(make_pair(r, c));
      }
    while (1) {
      a = bm.bfsAll(Q[idx]);
      if (a > 1)
        break;
      else if (a == 0) {
        ans = 0;
        break;
      }
      ans++;
      X.resize(0);
      Q[1 - idx].resize(0);
      for (i = 0; i < Q[idx].size(); i++) {
        r = Q[idx][i].first;
        c = Q[idx][i].second;
        a = 0;
        for (j = 0; j < 4; j++) {
          r2 = r + dr[j];
          c2 = c + dc[j];
          if (bm.getRC(r2, c2) == 0) a++;
        }
        X.push_back(a);
      }
      for (i = 0; i < Q[idx].size(); i++) {
        r = Q[idx][i].first;
        c = Q[idx][i].second;
        a = bm.getRC(r, c) - X[i];
        if (a <= 0) {
          a = 0;
        } else {
          Q[1 - idx].push_back(make_pair(r, c));
        }
        bm.setRC(r, c, a);
      }
      idx = 1 - idx;
    }
    printf("%d", ans);
  }
};
class Number {
 public:
  Number() {}
  int getDigitNum(long long xx) {
    long long x;
    int ret = 0;
    for (x = 1; x < xx; x *= 10, ret++)
      ;
    return ret;
  }
  int getDigitSum(int xx) {
    int x, a = 0;
    for (x = xx; x; x /= 10) a += (x % 10);
    return a;
  }
  int getMSB(long long xx) {
    int i;
    for (i = 0; (1ll << i) <= xx; i++)
      ;
    return i - 1;
  }
  long long convertBinaryToBase(long long x, int base) {
    if (x == 0) return 0;
    return base * convertBinaryToBase(x / 2, base) + (x % 2);
  }
  long long findFactor(long long k) {
    for (long long d = 2; d * d <= k; d++)
      if (k % d == 0) return d;
    return 0;
  }
};
class Palindrome {
 public:
  Palindrome() {}
  int isPalindrome(long long xx) {
    long long x;
    int i, n;
    vector<int> v;
    for (x = xx; x > 0; x /= 10) {
      v.push_back(x % 10);
    }
    n = v.size();
    for (i = 0; i < n / 2; i++) {
      if (v[i] != v[n - i - 1]) return 0;
    }
    return 1;
  }
};
class BigNumber {
 public:
  BigNumber() {}
  string add(string &s1, string &s2) {
    int i, j, k, n1, n2, a;
    string s3;
    vector<int> v;
    n1 = s1.size();
    n2 = s2.size();
    v.reserve(max(n1, n2) + 1);
    for (i = n1 - 1, j = n2 - 1; i >= 0 && j >= 0; i--, j--) {
      a = s1[i] - '0' + s2[j] - '0';
      v.push_back(a);
    }
    while (i >= 0) {
      a = s1[i] - '0';
      v.push_back(a);
      i--;
    }
    while (j >= 0) {
      a = s2[j] - '0';
      v.push_back(a);
      j--;
    }
    for (i = 0, a = 0; i < v.size(); i++) {
      a += v[i];
      if (a >= 10) {
        v[i] = a - 10;
        a = 1;
      } else {
        v[i] = a;
        a = 0;
      }
    }
    if (a) v.push_back(a);
    s3.reserve(v.size());
    for (i = v.size() - 1; i >= 0; i--) s3 += (char)(v[i] + '0');
    s3 += '\n';
    return s3;
  }
};
class PrimeNumber {
  int N;
  vector<int> NP, P;

 public:
  PrimeNumber() {}
  PrimeNumber(int n) {
    N = n;
    NP.reserve(N + 4);
    P.reserve(N / 4);
    for (int i = 2; i * i <= N; i++) {
      if (NP[i]) continue;
      for (int j = i * i; j <= N; j += i) NP[i] = 1;
    }
    for (int i = 2; i <= N; i++)
      if (!NP[i]) P.push_back(i);
  }
  long long gcd(long long x, long long y) {
    long long z;
    while (x) {
      z = y % x;
      y = x;
      x = z;
    }
    return y;
  }
  vector<int> factorization(int x) {
    vector<int> ret;
    int i;
    if (x == 1) {
      ret.push_back(1);
      return ret;
    }
    ret.push_back(1);
    ret.push_back(x);
    for (i = 2; i * i < x; i++) {
      if (x % i == 0) {
        ret.push_back(i);
        ret.push_back(x / i);
      }
    }
    if (i * i == x) ret.push_back(i);
    return ret;
  }
  int factorization2(int x) {
    int ret = 0, i;
    if (x == 1) {
      return 1;
    }
    ret = 2;
    for (i = 2; i * i < x; i++) {
      if (x % i == 0) {
        ret += 2;
      }
    }
    if (i * i == x) ret++;
    return ret;
  }
};
class BitOperation {
 public:
  BitOperation() {}
  int getOneBitNum(int xx) {
    int a = 0, x;
    for (x = xx; x; x = x & (x - 1)) a++;
    return a;
  }
};
class Comb {
  vector<vector<long long> > C;
  vector<long long> F;
  int N;

 public:
  Comb(int n) {
    N = n;
    C.resize(N + 1);
    for (int i = 0; i <= N; i++) C[i].resize(i + 1);
    for (int i = 0; i <= N; i++) C[i][i] = C[i][0] = 1;
    for (int i = 1; i <= N; i++)
      for (int j = 1; j < i; j++)
        C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % 998244353;
    F.resize(N + 1);
    F[0] = F[1] = 1;
    for (int i = 1; i <= n; i++) F[i] = (F[i - 1] * i) % 998244353;
  }
  long long getC(int n, int r) { return C[n][r]; }
  long long getF(int n) { return F[n]; }
  long long get_comb(int n, int r) {
    if (n == r || r == 0) return 1;
    if (n <= 1000) return getC(n, r);
    long long ret = 1;
    int i;
    if (r > n / 2) r = n - r;
    for (i = n; i > n - r; i--) ret *= i;
    for (i = 2; i <= r; i++) ret /= i;
    return ret;
  }
};
class Sort {
  vector<int> tmp;
  int N;

 public:
  Sort(int n) {
    N = n;
    tmp.reserve(n + 4);
  }
  void merge_sort(vector<int> &x, int lo, int hi) {
    if (lo >= hi) return;
    int i, j, k, mid = (lo + hi) / 2;
    merge_sort(x, lo, mid);
    merge_sort(x, mid + 1, hi);
    for (i = lo, j = mid + 1, k = lo; i <= mid && j <= hi; k++) {
      if (x[i] < x[j])
        tmp[k] = x[i++];
      else
        tmp[k] = x[j++];
    }
    if (i <= mid) {
      for (; i <= mid; i++, k++) tmp[k] = x[i];
    }
    if (j <= hi) {
      for (; j <= hi; j++, k++) tmp[k] = x[j];
    }
    for (i = lo; i <= hi; i++) x[i] = tmp[i];
  }
};
class PSum {
  PSum() {}
  vector<int> makeSum(const vector<int> &a, int n) {
    vector<int> ret(a.size());
    ret[0] = a[0];
    for (int i = 1; i < a.size(); ++i) ret[i] = ret[i - 1] + a[i];
    return ret;
  }
  vector<vector<int> > makeSum(const vector<vector<int> > &a, int n, int m) {
    vector<vector<int> > ret(n, vector<int>(m));
    int i, j;
    for (i = 0; i < n; i++) ret[i][0] = a[i][0];
    for (i = 0; i < n; i++) {
      for (j = 1; j < m; j++) {
        ret[i][j] = ret[i][j - 1] + a[i][j];
      }
    }
  }
  int getSum(const vector<int> &psum, int a, int b) {
    if (a == 0) return psum[b];
    return psum[b] - psum[a - 1];
  }
  int getSum(const vector<vector<int> > &psum, int r1, int c1, int r2, int c2) {
    int ret = psum[r2][c2];
    if (r1 > 0) ret -= psum[r1 - 1][c2];
    if (c1 > 0) ret -= psum[r2][c1 - 1];
    if (r1 > 0 && c1 > 0) ret += psum[r1 - 1][c1 - 1];
    return ret;
  }
};
class DisjointSet {
  int N;
  vector<int> P, R, A;

 public:
  DisjointSet(int n) {
    N = n;
    P = vector<int>(n + 1);
    R = vector<int>(n + 1);
    A = vector<int>(n + 1);
    for (int i = 1; i <= n; i++) P[i] = i, R[i] = 0, A[i] = 1;
  }
  int getA(int x) { return A[x]; }
  int find_set(int x) {
    if (P[x] == x) return x;
    int pa = find_set(P[x]);
    return P[x] = pa;
  }
  int union_set(int x, int y) {
    int px, py;
    px = find_set(x);
    py = find_set(y);
    if (px == py) return px;
    if (R[px] > R[py]) {
      P[py] = px;
      A[px] += A[py];
      return px;
    } else {
      P[px] = py;
      A[py] += A[px];
      if (R[px] == R[py]) R[py]++;
      return py;
    }
  }
};
class LIS {
  int N, BI;
  vector<int> A;

 public:
  LIS(int n) {
    N = n;
    A = vector<int>(n);
  }
  void setA(int x, int y) { A[x] = y; }
  int execute() {
    int i, lo, hi, x, vi;
    vector<int> v = vector<int>(N, 0);
    vi = -1;
    v[++vi] = A[0];
    for (i = 1; i < N; i++) {
      if (A[i] > v[vi]) {
        v[++vi] = A[i];
        continue;
      }
      for (lo = 0, hi = vi; lo < hi;) {
        if (v[(lo + hi) / 2] >= A[i])
          hi = (lo + hi) / 2;
        else
          lo = (lo + hi) / 2 + 1;
      }
      v[hi] = A[i];
    }
    return vi + 1;
  }
  vector<int> execute2(int &len) {
    vector<int> v, v1, p, ret;
    int i, j;
    v.push_back(A[0]);
    v1.push_back(0);
    p = vector<int>(N, -1);
    for (int i = 1; i < A.size(); i++) {
      if (v.back() < A[i]) {
        p[i] = v1.back();
        v.push_back(A[i]);
        v1.push_back(i);
      } else {
        vector<int>::iterator itr = lower_bound(v.begin(), v.end(), A[i]);
        *itr = A[i];
        int idx = itr - v.begin();
        if (idx != 0) {
          p[i] = v1[idx - 1];
        }
        v1[idx] = i;
      }
    }
    len = v1.size();
    ret = vector<int>(len);
    for (i = v1.back(), j = len - 1; i != -1; i = p[i], j--) ret[j] = A[i];
    return ret;
  }
  int execute3() {
    int i, j, ret = 0;
    vector<int> v = vector<int>(N, 0);
    for (i = 0; i < A.size(); i++) {
      for (j = 0; j < i; j++)
        if (A[j] < A[i] && v[i] < v[j]) v[i] = v[j];
      v[i]++;
    }
    for (i = 0; i < v.size(); i++)
      if (v[i] > ret) ret = v[i];
    return ret;
  }
  void g() {
    int T, i, j, k, a, b, c, d, e, f, g, n, m, x, y, z;
    long long il, jl, kl, al, bl, cl, dl, nl, ml, xl, yl;
    vector<int> v, v1, v2, v3, v4;
    vector<unsigned int> v5, v6;
    string s1, s2;
    vector<string> vs;
    scanf("%d", &n);
    v1 = vector<int>(n);
    LIS li(n);
    for (i = 0; i < n; i++) {
      scanf("%d", &v1[i]);
      li.setA(i, v1[i]);
    }
    v = li.execute2(x);
    printf("%d\n", x);
    for (i = 0; i < v.size(); i++) printf("%d ", v[i]);
  }
};
class SegmentTreeSum {
  vector<long long> ST;
  vector<int> A;
  int N;
  long long _init(vector<int> &a, int left, int right, int node) {
    if (left == right) return ST[node] = a[left];
    int mid = (left + right) / 2;
    long long lv = _init(a, left, mid, node * 2),
              rv = _init(a, mid + 1, right, node * 2 + 1);
    return ST[node] = lv + rv;
  }
  long long _query(int left, int right, int node, int nodeLeft, int nodeRight) {
    if (right < nodeLeft || nodeRight < left) return 0;
    if (left <= nodeLeft && nodeRight <= right) return ST[node];
    int mid = (nodeLeft + nodeRight) / 2;
    long long lv = _query(left, right, node * 2, nodeLeft, mid),
              rv = _query(left, right, node * 2 + 1, mid + 1, nodeRight);
    return lv + rv;
  }
  long long _update(int index, int newValue, int node, int nodeLeft,
                    int nodeRight) {
    if (index < nodeLeft || nodeRight < index) return ST[node];
    if (nodeLeft == nodeRight) return ST[node] = newValue;
    int mid = (nodeLeft + nodeRight) / 2;
    long long lv = _update(index, newValue, node * 2, nodeLeft, mid),
              rv = _update(index, newValue, node * 2 + 1, mid + 1, nodeRight);
    return ST[node] = lv + rv;
  }

 public:
  SegmentTreeSum(int n) {
    N = n;
    ST = vector<long long>(n * 4 + 4);
    A = vector<int>(n + 4);
  }
  void setA(int x, int y) { A[x] = y; }
  void init() { _init(A, 1, N, 1); }
  long long query(int left, int right) { return _query(left, right, 1, 1, N); }
  long long update(int index, int newValue) {
    return _update(index, newValue, 1, 1, N);
  }
};
class SegmentTreeMin {
  vector<long long> ST;
  vector<int> A;
  int N;
  long long _init(vector<int> &a, int left, int right, int node) {
    if (left == right) return ST[node] = a[left];
    int mid = (left + right) / 2;
    long long lv = _init(a, left, mid, node * 2),
              rv = _init(a, mid + 1, right, node * 2 + 1);
    return ST[node] = min(lv, rv);
  }
  long long _query(int left, int right, int node, int nodeLeft, int nodeRight) {
    if (right < nodeLeft || nodeRight < left) return 1000000007;
    if (left <= nodeLeft && nodeRight <= right) return ST[node];
    int mid = (nodeLeft + nodeRight) / 2;
    long long lv = _query(left, right, node * 2, nodeLeft, mid),
              rv = _query(left, right, node * 2 + 1, mid + 1, nodeRight);
    return min(lv, rv);
  }
  long long _update(int index, int newValue, int node, int nodeLeft,
                    int nodeRight) {
    if (index < nodeLeft || nodeRight < index) return ST[node];
    if (nodeLeft == nodeRight) return ST[node] = newValue;
    int mid = (nodeLeft + nodeRight) / 2;
    long long lv = _update(index, newValue, node * 2, nodeLeft, mid),
              rv = _update(index, newValue, node * 2 + 1, mid + 1, nodeRight);
    return ST[node] = min(lv, rv);
  }

 public:
  SegmentTreeMin(int n) {
    N = n;
    ST = vector<long long>(n * 4 + 4);
    A = vector<int>(n + 4);
  }
  void setA(int x, int y) { A[x] = y; }
  void init() { _init(A, 1, N, 1); }
  long long query(int left, int right) { return _query(left, right, 1, 1, N); }
  long long update(int index, int newValue) {
    return _update(index, newValue, 1, 1, N);
  }
};
class SegmentTreeMax {
  vector<long long> ST;
  vector<int> A;
  int N;
  long long _init(vector<int> &a, int left, int right, int node) {
    if (left == right) return ST[node] = a[left];
    int mid = (left + right) / 2;
    long long lv = _init(a, left, mid, node * 2),
              rv = _init(a, mid + 1, right, node * 2 + 1);
    return ST[node] = max(lv, rv);
  }
  long long _query(int left, int right, int node, int nodeLeft, int nodeRight) {
    if (right < nodeLeft || nodeRight < left) return 0;
    if (left <= nodeLeft && nodeRight <= right) return ST[node];
    int mid = (nodeLeft + nodeRight) / 2;
    long long lv = _query(left, right, node * 2, nodeLeft, mid),
              rv = _query(left, right, node * 2 + 1, mid + 1, nodeRight);
    return max(lv, rv);
  }
  long long _update(int index, int newValue, int node, int nodeLeft,
                    int nodeRight) {
    if (index < nodeLeft || nodeRight < index) return ST[node];
    if (nodeLeft == nodeRight) return ST[node] = newValue;
    int mid = (nodeLeft + nodeRight) / 2;
    long long lv = _update(index, newValue, node * 2, nodeLeft, mid),
              rv = _update(index, newValue, node * 2 + 1, mid + 1, nodeRight);
    return ST[node] = max(lv, rv);
  }

 public:
  SegmentTreeMax(int n) {
    N = n;
    ST = vector<long long>(n * 4 + 4);
    A = vector<int>(n + 4);
  }
  void setA(int x, int y) { A[x] = y; }
  void init() { _init(A, 1, N, 1); }
  long long query(int left, int right) { return _query(left, right, 1, 1, N); }
  long long update(int index, int newValue) {
    return _update(index, newValue, 1, 1, N);
  }
};
int L[20], R[20], N, M;
int f(int ff, int pp) {
  if (ff == N) {
    if (!pp) return R[ff];
    return M - L[ff] + 1;
  }
  if (!pp) {
    return min(f(ff + 1, 1) + M + 2, f(ff + 1, 0) + R[ff] * 2 + 1);
  } else {
    return min(f(ff + 1, 0) + M + 2, f(ff + 1, 1) + (M - L[ff] + 1) * 2 + 1);
  }
}
int main() {
  int i, j, k, n, m, A[4][4];
  char str[200];
  scanf("%d%d", &n, &M);
  N = 0;
  for (i = n; i >= 1; i--) {
    scanf("%s\n", str);
    for (j = 1; j <= M && str[j] == '0'; j++)
      ;
    if (j > M) {
      L[i] = M + 1;
      R[i] = 0;
      continue;
    }
    if (!N) N = i;
    L[i] = j;
    for (j = M; j >= 1 && str[j] == '0'; j--)
      ;
    R[i] = j;
  }
  if (!N)
    printf("0");
  else
    printf("%d", f(1, 0));
}
