#include #include #include #include #include #include #include #include #include #include using namespace std; #define int long long int MOD = 1000000007; int INF = (int)1 << 60; int dx[6] = { -1,-1,0,0,1,1 }; int dy[6] = { -1,0,-1,1,0,1 }; struct Sumvec { vector v; vector sum; void init(int N) { v.clear(); v.resize(N + 1, 0); } int update(int i, int k) { v[i + 1] = k; } int build() { sum.clear(); sum.resize(v.size(), 0); for (int i = 1; i < (int)sum.size(); i++) { sum[i] += sum[i - 1] + v[i]; } } int get(int a, int b) { return sum[b] - sum[a]; } }; signed main() { cin.tie(0); ios::sync_with_stdio(false); int N, K, P; cin >> N >> K >> P; vector >A(N, vector(N, INF)); int x, y; queue > qu; for (int i = 0; i < K; i++) { cin >> x >> y; x--; y--; A[x][y] = 0; qu.push(make_pair(x, y)); } while ((int)qu.size() > 0) { pair p = qu.front(); qu.pop(); pair q; for (int i = 0; i < 6; i++) { q.first = p.first + dx[i]; q.second = p.second + dy[i]; if (q.first >= 0 && q.first < N && q.second >= 0 && q.second <= q.first) { if (A[q.first][q.second] > A[p.first][p.second] + 1) { A[q.first][q.second] = A[p.first][p.second] + 1; qu.push(q); } } } } for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { A[i][j] = 0; } } for (int i = 0; i < N; i++) { for (int j = 0; j <= i; j++) { cerr << A[i][j] << " "; } cerr << endl; } vector h(N); for (int i = 0; i < N; i++) { h[i].init(i + 1); for (int j = 0; j < i + 1; j++) { h[i].update(j, A[i][j]); } h[i].build(); } vector l(N); for (int i = 0; i < N; i++) { l[i].init(N); for (int j = 0; j < N; j++) { l[i].update(j, A[j][i]); } l[i].build(); } vector r(N); for (int i = 0; i < N; i++) { r[i].init(N - i); for (int j = 0; j < N - i; j++) { r[i].update(j, A[j + i][j]); } r[i].build(); } int res = 0; vector >D(N, vector(N, INF)); vector >sc(N, vector(N, INF)); sc[0][0] = A[0][0]; int d = 0; //cerr << sc[0][0] << endl; //cerr << h[1].get(0, 2) << endl; //cerr << h[1].sum[0] << endl; //cerr << h[1].sum[2] << endl; while (sc[0][0] < P && d < N - 1) { d++; sc[0][0] += h[d].get(0, d + 1); //cerr << sc[0][0] << endl; } if (sc[0][0] >= P) { res += N - d; } D[0][0] = d; for (int i = 1; i < N; i++) { for (int j = 0; j <= i; j++) { int bb; if (j == 0) { bb = 0; } else if (j == i) { bb = -1; } else if (D[i - 1][j - 1] > D[i - 1][j]) { bb = -1; } else { bb = 0; } d = D[i - 1][j + bb]; sc[i][j] = sc[i - 1][j + bb]; if (d == N) { d--; } //cerr << bb << endl; if (bb == -1) { sc[i][j] -= l[j - 1].get(i - 1, d + 1); } else { //cerr << i - j - 1 << " " << j << " " << d - (i - 1 - j) + 1 << endl; sc[i][j] -= r[i - 1 - j].get(j, d - (i - 1 - j) + 1); } //cerr << i << " " << j << endl; while (sc[i][j] < P && d < N - 1) { d++; sc[i][j] += h[d].get(j, j + d - i + 1); } if (sc[i][j] >= P) { res += N - d; } D[i][j] = d; } } cout << res << endl; }