#include <bits/stdc++.h>
// #define int long long
#define fi first
#define se second
#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()
#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }
using ll = long long;
using pii = std::pair<int, int>;
const int NMAX = 3e4;
const int MMAX = 2e3;
using namespace std;
mt19937_64 rng(time(NULL));
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
unordered_set<int, custom_hash> G[NMAX + 5];
vector<int> T[NMAX + 5];
vector<pair<int, int>> edges;
int viz[NMAX + 5], mate[NMAX + 5], n, m, k;
bool try_match(int u) {
if (viz[u]) return false;
viz[u] = true;
for (auto &v : G[u]) {
if (mate[v] == -1 || try_match(mate[v])) {
mate[v] = u;
return true;
}
}
return false;
}
bool augment(int u) {
fill(viz + 1, viz + n + 1, 0LL);
return try_match(u);
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> m >> k;
for (int i = 0, girl, boy; i < k; ++i) {
cin >> boy >> girl;
T[boy].push_back(girl);
}
for (int v = 1; v <= n; ++v)
mate[v] = -1;
queue<int> to_match;
for (int u = 1; u <= m; ++u)
to_match.push(u);
int r = 0, ans = 0;
for (int l = 1; l <= n; ++l) {
while (!to_match.empty()) {
while (!to_match.empty() && augment(to_match.front()))
to_match.pop();
if (to_match.empty()) break;
if (r == n)
goto afis;
++r;
for (auto &girl : T[r])
G[girl].insert(r);
}
ans += (n - r + 1);
for (auto &girl : T[l])
G[girl].erase(l);
if (mate[l] != -1) {
to_match.push(mate[l]);
mate[l] = -1;
}
}
afis:
cout << ans << '\n';
return 0;
}
