rt，，不懂哪里假了，最后两个 sub tle。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 7e3 + 5, M = N * 15;
const ll inf = 1ll << 60;

int n;
ll m;
vector<ll> factors, pri;
ll in[N], out[N];

struct Flow {
	int h[N], to[M * 2], nxt[M * 2], cnt;
	ll val[M * 2];
	int cur[N], d[N];
	int vtot, S, T;
	void init(int _vtot, int _S, int _T) {
		vtot = _vtot, S = _S, T = _T, cnt = 1;
	}
	void add(int u, int v, ll w) {
		to[++ cnt] = v, val[cnt] = w, nxt[cnt] = h[u], h[u] = cnt;
		assert(cnt < 2 * M);
	}
	void addedge(int u, int v, ll w) {
		add(u, v, w), add(v, u, 0);
	}
	bool bfs() {
		for (int i = 0; i < vtot; i ++) d[i] = -1;
		d[S] = 0, cur[S] = h[S];
		queue<int> q;
		q.push(S);
		while (q.size()) {
			int u = q.front();
			q.pop();
			for (int i = h[u]; i; i = nxt[i]) {
				int v = to[i];
				if (d[v] == -1 && val[i]) {
					d[v] = d[u] + 1;
					cur[v] = h[v];
					if (v == T) return true;
					q.push(v);
				}
			}
		}
		return false;
	}
	ll dfs(int u, ll lim) {
		if (u == T) return lim;
		ll flow = 0;
		for (int i = cur[u]; i && flow < lim; i = nxt[i]) {
			cur[u] = i;
			int v = to[i];
			if (d[v] == d[u] + 1 && val[i]) {
				int t = dfs(v, min(val[i], lim - flow));
				if (!t) d[v] = -1;
				flow += t, val[i] -= t, val[i ^ 1] += t;
			}
		}
		return flow;
	}
	ll dinic() {
		ll flow, r = 0;
		while (bfs()) while (flow = dfs(S, inf)) r += flow;
		return r;
	}
} g;

void init() {
	for (ll i = 1; i <= m / i; i ++) {
		if (m % i == 0) {
			factors.push_back(i);
			if (i * i != m) factors.push_back(m / i);
		}
	}
	sort(factors.begin(), factors.end());
	ll x = m;
	for (ll i = 2; i <= x / i; i ++) {
		if (x % i == 0) {
			pri.push_back(i);
			while (x % i == 0) x /= i;
		}
	}
	if (x != 1) pri.push_back(x);
}

ll get_phi(ll x) {
	ll phi = x;
	for (auto p : pri) {
		if (x % p == 0) {
			phi /= p, phi *= p - 1;
			while (x % p == 0) x /= p;
		}
	}
	return phi;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    init();
    for (int i = 1; i <= n; i ++) {
    	ll a, c;
    	cin >> a >> c;
    	a = __gcd(a, m);
    	int x = lower_bound(factors.begin(), factors.end(), a) - factors.begin();
    	in[x] += c;
    }
    int S = factors.size() + 1, T = S + 1;
    for (int i = 0; i < S; i ++) out[i] = get_phi(m / factors[i]);
    g.init(T + 1, S, T);
	for (int i = 0; i < S; i ++) {
		g.addedge(S, i, in[i]);
		g.addedge(i, T, out[i]);
	}
	for (int i = 0; i < S; i ++) {
		ll x = factors[i];
		for (auto p : pri) {
			if (x % p == 0) {
				ll j = lower_bound(factors.begin(), factors.end(), x / p) - factors.begin();
				g.addedge(j, i, inf);
			}
		}
	}

	cout << g.dinic() << "\n";

    return 0;
}