#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using namespace atcoder; typedef long long ll; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define repr(i, n) for (int i = (int)(n)-1; i >= 0; i--) #define repk(i, k, n) for (int i = k; i < (int)(n); i++) #define all(v) v.begin(), v.end() #define mod1 1000000007 #define mod2 998244353 #define mod3 100000007 #define vi vector #define vs vector #define vc vector #define vl vector #define vb vector #define vvi vector> #define vvc vector> #define vvl vector> #define vvb vector> #define vvvi vector>> #define vvvl vector>> #define pii pair #define pil pair #define pli pair #define pll pair #define vpii vector> #define vpll vector> #define vvpii vector>> #define vvpll vector>> using mint = modint998244353; template void debug(T e) { cerr << e << endl; } template void debug(vector &v) { rep(i, v.size()) { cerr << v[i] << " "; } cerr << endl; } template void debug(vector> &v) { rep(i, v.size()) { rep(j, v[i].size()) { cerr << v[i][j] << " "; } cerr << endl; } } template void debug(vector> &v) { rep(i, v.size()) { cerr << v[i].first << " " << v[i].second << endl; } } template void debug(set &st) { for (auto itr = st.begin(); itr != st.end(); itr++) { cerr << *itr << " "; } cerr << endl; } template void debug(multiset &ms) { for (auto itr = ms.begin(); itr != ms.end(); itr++) { cerr << *itr << " "; } cerr << endl; } template void debug(map &mp) { for (auto itr = mp.begin(); itr != mp.end(); itr++) { cerr << itr->first << " " << itr->second << endl; } } void debug_out() { cerr << endl; } template void debug_out(Head H, Tail... T) { cerr << H << " "; debug_out(T...); } ll INF = 1000000000; int main() { ll H, W; cin >> H >> W; assert(1 <= H && H <= 200); assert(1 <= W && W <= 200); vector a(W); vector b(W); map mp; for (ll i = 0; i < W; i++) { cin >> a[i] >> b[i]; assert(1 <= a[i] && a[i] <= H); assert(1 <= b[i] && b[i] <= W + a[i] - 1); a[i]--; b[i]--; assert(mp[pll(a[i], b[i])] == 0); mp[pll(a[i], b[i])]++; } queue que; vector> dists(W, vector(W)); vector> dist(H, vector(H + W, INF)); vector dx = {-1, -1, 0, 0, 1, 1}; vector dy = {-1, 0, -1, 1, 0, 1}; for (ll i = 0; i < W; i++) { for (ll j = 0; j < H; j++) { for (ll k = 0; k < H + W; k++) { dist[j][k] = INF; } } dist[a[i]][b[i]] = 0; que.push(pll(a[i], b[i])); while (que.size()) { pll p = que.front(); que.pop(); ll px = p.first; ll py = p.second; for (ll j = 0; j < 6; j++) { if (px + dx[j] >= 0 && px + dx[j] < H && py + dy[j] >= 0 && py + dy[j] < W + px + dx[j]) { if (dist[px + dx[j]][py + dy[j]] < INF) { continue; } dist[px + dx[j]][py + dy[j]] = dist[px][py] + 1; que.push(pll(px + dx[j], py + dy[j])); } } } // debug(dist); for (ll j = 0; j < W; j++) { dists[i][j] = dist[0][j]; } } debug(dists); mcf_graph graph(2 * W + 2); for (ll i = 0; i < W; i++) { for (ll j = 0; j < W; j++) { graph.add_edge(i, W + j, 1, dists[i][j]); } } for (ll i = 0; i < W; i++) { graph.add_edge(2 * W, i, 1, 0); } for (ll i = 0; i < W; i++) { graph.add_edge(W + i, 2 * W + 1, 1, 0); } pll flp = graph.flow(2 * W, 2 * W + 1); cout << flp.second << endl; }