观察性质 + 奇偶分类构造二分图+ 二分图匹配：0109C

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135489832

http://cplusoj.com/d/senior/p/SS240109C

通过手模可知 $f(a) + 2C = f(a + 2C)$

于是这题很多时候要在模 $2C$ 意义下讨论。

假设 $i$ 位置放 $k$ ，则 $2k-i+1$ 位置 $k+c$ 。而在模 $2C$ 意义下只有这两个位置是互相联系的。所以一个朴素思路是点对配对。

配对的贡献是容易算的。假设 $i,j$ 配对， $i$ 位置放 $k$ ，则 $2k-i+1$ 位置为 $k+c$ ， $j$ 位置为 $k+c+j-(2k-i+1)$ 。和 $i$ 同余的位为 $|k+x-i-y|$ ，和 $j$ 同余的贡献为 $|k+c+j-(2k-i+1)+x-j+y|$ 。显然只有 $k$ 是变量，于是就变成了一堆绝对值方程求最小值，显然中位数。但同时必须满足 $2k-i+1\equiv j\pmod p$

但是如何构造匹配，这就是此题的精髓了。 注意到 $i$ 和 $2k-i+1$ 奇偶性不同，然后就可以构造二分图了！

因为我们有了贡献，所以直接跑二分图最大权完美匹配即可。

#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
namespace atcoder {
	namespace internal {

		template <class E> struct csr {
			std::vector<int> start;
			std::vector<E> elist;
			explicit csr(int n, const std::vector<std::pair<int, E>>& edges)
				: start(n + 1), elist(edges.size()) {
				for (auto e : edges) {
					start[e.first + 1]++;
				}
				for (int i = 1; i <= n; i++) {
					start[i] += start[i - 1];
				}
				auto counter = start;
				for (auto e : edges) {
					elist[counter[e.first]++] = e.second;
				}
			}
		};

	}  // namespace internal
	namespace internal {

		template <class T> struct simple_queue {
			std::vector<T> payload;
			int pos = 0;
			void reserve(int n) {
				payload.reserve(n);
			}
			int size() const {
				return int(payload.size()) - pos;
			}
			bool empty() const {
				return pos == int(payload.size());
			}
			void push(const T& t) {
				payload.push_back(t);
			}
			T& front() {
				return payload[pos];
			}
			void clear() {
				payload.clear();
				pos = 0;
			}
			void pop() {
				pos++;
			}
		};

	}  // namespace internal


	template <class Cap, class Cost> struct mcf_graph {
		public:
			mcf_graph() {}
			explicit mcf_graph(int n) : _n(n) {}

			int add_edge(int from, int to, Cap cap, Cost cost) {
				assert(0 <= from && from < _n);
				assert(0 <= to && to < _n);
				assert(0 <= cap);
				assert(0 <= cost);
				int m = int(_edges.size());
				_edges.push_back({from, to, cap, 0, cost});
				return m;
			}

			struct edge {
				int from, to;
				Cap cap, flow;
				Cost cost;
			};

			edge get_edge(int i) {
				int m = int(_edges.size());
				assert(0 <= i && i < m);
				return _edges[i];
			}
			std::vector<edge> edges() {
				return _edges;
			}

			std::pair<Cap, Cost> flow(int s, int t) {
				return flow(s, t, std::numeric_limits<Cap>::max());
			}
			std::pair<Cap, Cost> flow(int s, int t, Cap flow_limit) {
				return slope(s, t, flow_limit).back();
			}
			std::vector<std::pair<Cap, Cost>> slope(int s, int t) {
				return slope(s, t, std::numeric_limits<Cap>::max());
			}
			std::vector<std::pair<Cap, Cost>> slope(int s, int t, Cap flow_limit) {
				assert(0 <= s && s < _n);
				assert(0 <= t && t < _n);
				assert(s != t);

				int m = int(_edges.size());
				std::vector<int> edge_idx(m);

				auto g = [&]() {
					std::vector<int> degree(_n), redge_idx(m);
					std::vector<std::pair<int, _edge>> elist;
					elist.reserve(2 * m);
					for (int i = 0; i < m; i++) {
						auto e = _edges[i];
						edge_idx[i] = degree[e.from]++;
						redge_idx[i] = degree[e.to]++;
						elist.push_back({e.from, {e.to, -1, e.cap - e.flow, e.cost}});
						elist.push_back({e.to, {e.from, -1, e.flow, -e.cost}});
					}
					auto _g = internal::csr<_edge>(_n, elist);
					for (int i = 0; i < m; i++) {
						auto e = _edges[i];
						edge_idx[i] += _g.start[e.from];
						redge_idx[i] += _g.start[e.to];
						_g.elist[edge_idx[i]].rev = redge_idx[i];
						_g.elist[redge_idx[i]].rev = edge_idx[i];
					}
					return _g;
				}();

				auto result = slope(g, s, t, flow_limit);

				for (int i = 0; i < m; i++) {
					auto e = g.elist[edge_idx[i]];
					_edges[i].flow = _edges[i].cap - e.cap;
				}

				return result;
			}

		private:
			int _n;
			std::vector<edge> _edges;

			// inside edge
			struct _edge {
				int to, rev;
				Cap cap;
				Cost cost;
			};

			std::vector<std::pair<Cap, Cost>> slope(internal::csr<_edge>& g,
			                                        int s,
			                                        int t,
			Cap flow_limit) {
				// variants (C = maxcost):
				// -(n-1)C <= dual[s] <= dual[i] <= dual[t] = 0
				// reduced cost (= e.cost + dual[e.from] - dual[e.to]) >= 0 for all edge

				// dual_dist[i] = (dual[i], dist[i])
				std::vector<std::pair<Cost, Cost>> dual_dist(_n);
				std::vector<int> prev_e(_n);
				std::vector<bool> vis(_n);
				struct Q {
					Cost key;
					int to;
					bool operator<(Q r) const {
						return key > r.key;
					}
				};
				std::vector<int> que_min;
				std::vector<Q> que;
				auto dual_ref = [&]() {
					for (int i = 0; i < _n; i++) {
						dual_dist[i].second = std::numeric_limits<Cost>::max();
					}
					std::fill(vis.begin(), vis.end(), false);
					que_min.clear();
					que.clear();

					// que[0..heap_r) was heapified
					size_t heap_r = 0;

					dual_dist[s].second = 0;
					que_min.push_back(s);
					while (!que_min.empty() || !que.empty()) {
						int v;
						if (!que_min.empty()) {
							v = que_min.back();
							que_min.pop_back();
						} else {
							while (heap_r < que.size()) {
								heap_r++;
								std::push_heap(que.begin(), que.begin() + heap_r);
							}
							v = que.front().to;
							std::pop_heap(que.begin(), que.end());
							que.pop_back();
							heap_r--;
						}
						if (vis[v]) continue;
						vis[v] = true;
						if (v == t) break;
						// dist[v] = shortest(s, v) + dual[s] - dual[v]
						// dist[v] >= 0 (all reduced cost are positive)
						// dist[v] <= (n-1)C
						Cost dual_v = dual_dist[v].first, dist_v = dual_dist[v].second;
						for (int i = g.start[v]; i < g.start[v + 1]; i++) {
							auto e = g.elist[i];
							if (!e.cap) continue;
							// |-dual[e.to] + dual[v]| <= (n-1)C
							// cost <= C - -(n-1)C + 0 = nC
							Cost cost = e.cost - dual_dist[e.to].first + dual_v;
							if (dual_dist[e.to].second - dist_v > cost) {
								Cost dist_to = dist_v + cost;
								dual_dist[e.to].second = dist_to;
								prev_e[e.to] = e.rev;
								if (dist_to == dist_v) {
									que_min.push_back(e.to);
								} else {
									que.push_back(Q {dist_to, e.to});
								}
							}
						}
					}
					if (!vis[t]) {
						return false;
					}

					for (int v = 0; v < _n; v++) {
						if (!vis[v]) continue;
						// dual[v] = dual[v] - dist[t] + dist[v]
						//         = dual[v] - (shortest(s, t) + dual[s] - dual[t]) +
						//         (shortest(s, v) + dual[s] - dual[v]) = - shortest(s,
						//         t) + dual[t] + shortest(s, v) = shortest(s, v) -
						//         shortest(s, t) >= 0 - (n-1)C
						dual_dist[v].first -= dual_dist[t].second - dual_dist[v].second;
					}
					return true;
				};
				Cap flow = 0;
				Cost cost = 0, prev_cost_per_flow = -1;
				std::vector<std::pair<Cap, Cost>> result = {{Cap(0), Cost(0)}};
				while (flow < flow_limit) {
					if (!dual_ref()) break;
					Cap c = flow_limit - flow;
					for (int v = t; v != s; v = g.elist[prev_e[v]].to) {
						c = std::min(c, g.elist[g.elist[prev_e[v]].rev].cap);
					}
					for (int v = t; v != s; v = g.elist[prev_e[v]].to) {
						auto& e = g.elist[prev_e[v]];
						e.cap += c;
						g.elist[e.rev].cap -= c;
					}
					Cost d = -dual_dist[s].first;
					flow += c;
					cost += c * d;
					if (prev_cost_per_flow == d) {
						result.pop_back();
					}
					result.push_back({flow, cost});
					prev_cost_per_flow = d;
				}
				return result;
			}
	};

}  // namespace atcoder
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
int n, m, i, j, k, T, C;

namespace Sol1 {
	#define N 10010
	int x, y, d[N], mid, ans; 
	void Main() {
		for(i = 1; i <= n; ++i) {
			x = read(); y = read(); 
			d[i] = y - x; 
			if(x & 1) d[i] = -d[i]; 
		}
		sort(d + 1, d + n + 1); 
		mid = (n + 1) >> 1; k = -d[mid]; 
		for(i = 1; i <= n; ++i) d[i] += k; 
		for(i = 1; i <= n; ++i) ans += abs(d[i]); 
		printf("%lld", ans); 
	}
	#undef N
}

namespace Sol2 {
	#define N 50
	int ans = 1e18, sum, mid; 
	int b[N], a[N], us[N], x, y; 
	vector<int>G[N]; 
	int Mod(int k) {
		return (k % (2 * C) + 2 * C) % (2 * C); 
	}
	int suan(vector<int>&h, int k) {
		int sum = 0; 
		for(auto t : h) sum += abs(t - k); 
		return sum; 
	}
	void check() {
		for(i = 0; i < 2 * C; ++i) {
			k = a[i] * 2 - i + 1; k = Mod(k); 
			if(a[k] != Mod(a[i] + C)) return ; 
		}
//		for(i = 0; i < 2 * C; ++i) debug("%lld ", a[i]); debug("\n"); 
		for(i = sum = 0; i < 2 * C; ++i) {
			if(i & 1) continue; 		
			vector<int>h; 
			k = a[i] * 2 - i + 1; k = Mod(k); 
			for(auto t : G[i]) h.pb(a[i] + t); 
			for(auto t : G[k]) h.pb(a[i] + t + C); 
			if(h.empty()) continue; 
			sort(h.begin(), h.end()); m = h.size(); mid = (m + 1) >> 1; --mid; 
			j = h[mid]; j /= C; 
			sum += min(suan(h, j * C), suan(h, (j + 1) * C)); 
//			for(auto t : h) debug("%lld ", t); debug("\n"); 
//			for(auto t : h) sum += abs(t + j); 
			if(sum > ans) return ; 
		}
//		debug(">> %lld\n", sum); 
		ans = min(ans, sum); 
	}
	void dfs(int x) {
		if(x >= 2 * C) {
			check(); 
			return ; 
		}
		for(int i = 0; i < 2 * C; ++i) {
	 		a[x] = i; 
	 		dfs(x + 1); 
		}
	}
	void Main() {
		for(i = 1; i <= n; ++i) {
			x = read(); y = read(); 
			k = (x % (2 * C) + (2 * C)) % (2 * C); 
			G[k].pb(x - k - y); 
		}
		for(i = 0; i < 2 * C; ++i, debug("\n")) 
			for(auto t : G[i]) debug("%lld ", t); 
		dfs(0); 
		printf("%lld", ans); 
	}
	#undef N
}

namespace Sol3 {
	int ans, a1, mid, x, y, S; 
	vector<int> G[610]; 
	int Mod(int k) {
		return (k % (2 * C) + 2 * C) % (2 * C); 
	}
	int suan(vector<int>&h, int k) {
		int sum = 0; 
		for(auto t : h) sum += abs(k - t); 
		return sum; 
	}
	int calc(int i, int j) {
		vector<int>h; 
		a1 = (i + j - 1) / 2; a1 = Mod(a1); 
		for(auto t : G[i]) h.pb(t); 
		for(auto t : G[j]) h.pb(- j - i + 1 - t - C); 
		for(auto &t : h) t = -t; 
		sort(h.begin(), h.end()); m = h.size(); mid = (m + 1) >> 1; --mid; 
		if(h.empty()) return 0; 
//		for(auto t : h) debug("%lld ", t); 
//		if(a1 == 0) a1 = 2 * C; 
		int p = h[mid] / C; 
//		debug("|| %lld | %lld %lld\n", p, p * C, (p + 1) * C); 、 
		int ans = 1e18; 
		for(int i = -5; i <= 5; ++i) ans = min(ans, suan(h, (p + i) * C + a1)); 
		return ans; 
//		return min({suan(h, p * C), suan(h, (p + 1) * C, suan(h, (p - 1) * C)}); 
	}
	void Main() {
		for(i = 1; i <= n; ++i) {
			x = read(); y = read(); 
			k = (x % (2 * C) + (2 * C)) % (2 * C); 
			G[k].pb(x - k - y); 
		}
		atcoder :: mcf_graph<int, int>G(2 * C + 10);
		S = 2 * C; T = S + 1; 
		for(i = 0; i < 2 * C; i += 2) G.add_edge(S, i, 1, 0); 
		for(i = 1; i < 2 * C; i += 2) G.add_edge(i, T, 1, 0); 
		
		for(i = 0; i < 2 * C; i += 2)
			for(j = 1; j < 2 * C; j += 2) {
//				G.add_edge(i, j, 1, min(calc(i, j), calc(j, i))); 
				G.add_edge(i, j, 1, calc(i, j)); 
				debug("%lld <-> %lld ===> %lld\n", i, j, calc(i, j)); 
			}
		auto t = G.flow(S, T); 
		debug("%lld ", t.fi); 
		printf("%lld", t.se); 
	}
}

signed main()
{
	freopen("function.in", "r", stdin);
	freopen("function.out", "w", stdout);
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	n = read(); C = read(); 
//	if(n <= 4 && C <= 4) return Sol2 :: Main(), 0; 
//	if(C == 1) return Sol1 :: Main(), 0; 
//	if(n == 1) return printf("0"), 0; 
	Sol3 :: Main(); 
	return 0;
}