#include<iostream> #include<queue> #include<vector> #include<algorithm> using namespace std; vector<int> mt; vector<vector<int>> g; vector<int> mt1; int L = 0, R = 0; vector<bool> used; bool dfs(int v) { if (used[v]) return false; used[v] = true; for (auto u : g[v]) { if (L <= u && u <= R) { if (mt[u] == -1 || dfs(mt[u])) { mt[u] = v; mt1[v] = u; return true; } } } return false; } int main() { int m, n, k; cin >> m >> n >> k; g.resize(n); while (k--) { int u, v; cin >> u >> v; --u, --v; g[v].push_back(u); } used.resize(n); mt = vector<int>(m, -1); mt1 = vector<int>(n, -1); queue<int> q; for (int i = 0; i < n; ++i) { q.push(i); } long long ans = 0; for (L = 0, R = -1; max(R, L) < m;) { while (max(R, L) < m && !q.empty()) { while (!q.empty()) { int v = q.front(); used = vector<bool>(n, false); if (dfs(v)) { q.pop(); } else break; } if (q.empty()) break; R++; } ans += m - R; int v0 = mt[L]; if (v0 != -1) { mt[L] = -1; q.push(v0); } L++; } cout << ans; }