Problem: Taro loves chocolate and when he returns from school he eats his favorite chocolate bar with a heart symbol on it. A recent pleasure is to eat all the heart symbol blocks to the end. Taro , Try to eat as many heartless blocks as possible, with all heartmark blocks connected.

<image>

However, Taro is still young, and even if he tries to eat as above, useless blocks will remain. Therefore, Taro seeks the maximum number of blocks that can be eaten when all the heart-shaped blocks are left connected. I asked you to create a program.

Taro can eat whatever way he wants, as long as all the heart-shaped blocks are connected. If one side of one block does not touch the other block, it will be separated.



Input

The input consists of multiple datasets, each dataset given in the following format:


H W
H x W numbers


H and W are integers indicating the vertical size and horizontal size of the chocolate bar, respectively. H x W numbers represent block information, '0' representing blocks without a heart mark, and blocks with a heart mark. Consists of '1'.

The end of the input is indicated by the dataset where H = W = 0. Do not output for this case.

You can assume that 1 ≤ H, W ≤ 12 and the number of heart-shaped blocks is 6 or less.

Output

For each dataset, output the maximum number of blocks that Taro can eat.

Example

Input

4 4
1 0 0 0
0 0 1 0
0 1 0 0
1 0 0 1
1 1
1
2 3
1 0 0
0 0 1
0 0


Output

7
0
2

Solution (in CPP):

Solution:
// includes
#include <bits/stdc++.h>
using namespace std;

// macros
#define pb emplace_back
#define mk make_pair
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for(int i=((int)(n)-1);i>=0;i--)
#define irep(itr, st) for(auto itr = (st).begin(); itr != (st).end(); ++itr)
#define irrep(itr, st) for(auto itr = (st).rbegin(); itr != (st).rend(); ++itr)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define bit(n) (1LL<<(n))
// functions
template <class T>bool chmax(T &a, const T &b){if(a < b){a = b; return 1;} return 0;}
template <class T>bool chmin(T &a, const T &b){if(a > b){a = b; return 1;} return 0;}
template <typename T> istream &operator>>(istream &is, vector<T> &vec){for(auto &v: vec)is >> v; return is;}
template <typename T> ostream &operator<<(ostream &os, const vector<T>& vec){for(int i = 0; i < vec.size(); i++){ os << vec[i]; if(i + 1 != vec.size())os << " ";} return os;}
template <typename T> ostream &operator<<(ostream &os, const set<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;}
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;}
template <typename T> ostream &operator<<(ostream &os, const multiset<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;}
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;}
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p){os << p.first << " " << p.second; return os;}
template <typename T1, typename T2> ostream &operator<<(ostream &os, const map<T1, T2> &mp){for(auto itr = mp.begin(); itr != mp.end(); ++itr){ os << itr->first << ":" << itr->second; auto titr = itr; if(++titr != mp.end())os << " "; } return os;}
template <typename T1, typename T2> ostream &operator<<(ostream &os, const unordered_map<T1, T2> &mp){for(auto itr = mp.begin(); itr != mp.end(); ++itr){ os << itr->first << ":" << itr->second; auto titr = itr; if(++titr != mp.end())os << " "; } return os;}
//  types
using ll = long long int;
using P = pair<int, int>;
// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;
const int mod = 1000000007;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};
// io
struct fast_io{
  fast_io(){ios_base::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(20);}
} fast_io_;

template <typename T>
struct Graph {
  int n;
  vector<vector<T> > d;
  vector<vector<int> > path;
  Graph(int n): n(n) {
    d = vector<vector<T>>(n, vector<T>(n, numeric_limits<T>::max() / 10));
    path = vector<vector<int>>(n, vector<int>(n, -1));
    for(int i = 0; i < n; i++)d[i][i] = 0;
  }
  void warshall_floyd(){
    for(int k = 0; k < n; k++){
      for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
          if(d[i][j] > d[i][k] + d[k][j]){
            d[i][j] = d[i][k] + d[k][j];
            path[i][j] = k;
          }
        }
      }
    }
  }
  void adde(int at, int to, T cost){
    d[at][to] = cost;
  }
  vector<T>& operator[](size_t i){
    return d[i];
  }
};

using GraphI = Graph<int>;
using GraphL = Graph<ll>;

template <typename T>
struct SteinerTree{
  int n;
  vector<vector<T>> d;
  T inf = numeric_limits<T>::max() / 10;
  explicit SteinerTree(int n): n(n){
    d.resize(n, vector<T>(n, inf));
    for(int i = 0; i < n; i++)d[i][i] = 0;
  }
  void adde(int from, int to, T cost){
    d[from][to] = min(d[from][to], cost);
  }
  T steiner_tree(const vector<int> &v){
    if(v.size() == 1)return 0;
    // warshall floyd
    Graph<T> g(n);
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        if(i != j && d[i][j] != inf)g.adde(i, j, d[i][j]);
      }
    }
    g.warshall_floyd();

    int t = v.size();
    vector<vector<T>> opt(1 << t, vector<T>(n, inf));
    for(int i = 0; i < t; i++){
      for(int j = 0; j < n; j++){
        opt[1 << i][j] = g.d[v[i]][j];
      }
    }

    for(int s = 0; s < (1 << t); s++){
      if(!(s & (s - 1)))continue;
      for(int p = 0; p < n; p++){
        for(int u = s; ; u = (u - 1) & s){
          opt[s][p] = min(opt[s][p], opt[u][p] + opt[s - u][p]);
          if(u == 0)break;
        }
      }
      for(int p = 0; p < n; p++){
        for(int q = 0; q < n; q++){
          opt[s][p] = min(opt[s][p], opt[s][q] + g.d[p][q]);
        }
      }
    }
    T res = inf;
    for(int s = 0; s < (1 << t); s++){
      for(int p = 0; p < n; p++){
        res = min(res, opt[s][p] + opt[(1<<t)-1-s][p]);
      }
    }
    return res;
  }
};

int c[12][12];

int main(int argc, char const* argv[])
{
  int h, w;
  while(true){
    cin >> h >> w;
    if(h == 0 && w == 0)break;
    SteinerTree<int> st(h * w);
    vector<int> v;
    rep(i, h){
      rep(j, w){
        cin >> c[i][j];
        if(c[i][j] == 1)v.pb(i * w + j);
      }
    }
    rep(i, h){
      rep(j, w){
        rep(k, 4){
          int nx = i + dx[k];
          int ny = j + dy[k];
          if(nx >= 0 && nx < h && ny >= 0 && ny < w){
            st.adde(i * w + j, nx * w + ny, 1);
          }
        }
      }
    }
    int res = h * w - st.steiner_tree(v) - 1;
    cout << res << endl;
  }
  return 0;
}