// Source: https://usaco.guide/general/io #include <bits/stdc++.h> using namespace std; using ll = long long; #define eb emplace_back // faster than push_back xD // pbds UwU #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #define oset tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> // use pair for ms // my io library :D #define m1(x) template<class T, class... U> void x(T&& a, U&&... b) #define m2(x) (ll[]){(x forward<U>(b),0)...} m1(pr){cout << forward<T>(a); m2(cout << " " <<); cout << "\n";} m1(re){cin >> forward<T>(a); m2(cin >>);} int main() { ios::sync_with_stdio(0); cin.tie(0); ll n; re(n); vector<pair<ll,ll>> points(2*n); for (ll i{}; i < 2*n; i++){ ll x, y; re(x, y); points[i] = {x,y}; } vector<pair<ll,ll>> target; for (ll x = 1; x <= n; x++) { target.eb(x, 1); } for (ll x = 1; x <= n; x++) { target.eb(x, 2); } vector<vector<ll>> cost(2*n, vector<ll>(2*n)); for (ll i{}; i < 2*n; i++) { for (ll j{}; j < 2*n; j++) { cost[i][j] = abs(points[i].first - target[j].first) + abs(points[i].second - target[j].second); } } vector<ll> dp(1<<(2*n), 1e18); dp[0] = 0; for (ll mask{}; mask < 1<<(2*n); mask++){ ll i = __builtin_popcountll(mask); for (ll j{}; j < 2*n; j++){ if (!(mask & (1<<j))){ dp[mask | (1<<j)] = min(dp[mask | (1<<j)], dp[mask]+cost[i][j]); } } } pr(dp[(1<<(2*n)) - 1]); }