Paul is at the orchestra. The string section is arranged in an r × c rectangular grid and is filled with violinists with the exception of n violists. Paul really likes violas, so he would like to take a picture including at least k of them. Paul can take a picture of any axis-parallel rectangle in the orchestra. Count the number of possible pictures that Paul can take.

Two pictures are considered to be different if the coordinates of corresponding rectangles are different.


-----Input-----

The first line of input contains four space-separated integers r, c, n, k (1 ≤ r, c, n ≤ 10, 1 ≤ k ≤ n) — the number of rows and columns of the string section, the total number of violas, and the minimum number of violas Paul would like in his photograph, respectively.

The next n lines each contain two integers x_{i} and y_{i} (1 ≤ x_{i} ≤ r, 1 ≤ y_{i} ≤ c): the position of the i-th viola. It is guaranteed that no location appears more than once in the input.


-----Output-----

Print a single integer — the number of photographs Paul can take which include at least k violas. 


-----Examples-----
Input
2 2 1 1
1 2

Output
4

Input
3 2 3 3
1 1
3 1
2 2

Output
1

Input
3 2 3 2
1 1
3 1
2 2

Output
4



-----Note-----

We will use '*' to denote violinists and '#' to denote violists.

In the first sample, the orchestra looks as follows 

*#

**

 Paul can take a photograph of just the viola, the 1 × 2 column containing the viola, the 2 × 1 row containing the viola, or the entire string section, for 4 pictures total.

In the second sample, the orchestra looks as follows 

#*

*#

#*

 Paul must take a photograph of the entire section.

In the third sample, the orchestra looks the same as in the second sample.

Difficulty: EASY
Tags: Implementation

Complete search
Skill types: Complete search

Starter code:

Solutions:
f = lambda : map(int, input().split())
(r, c, n, k) = f()
t = [[0] * (c + 1) for i in range(r + 1)]
for j in range(n):
	(y, x) = f()
	t[y][x] = 1
for y in range(r):
	p = t[y + 1]
	for x in range(c):
		p[x + 1] += p[x]
	t[y + 1] = [a + b for (a, b) in zip(p, t[y])]
s = (c * c + c) * (r * r + r) >> 2
for y in range(r):
	for x in range(c):
		for a in range(1, c - x + 1):
			for b in range(1, r - y + 1):
				if t[y + b][x + a] + t[y][x] - t[y + b][x] - t[y][x + a] >= k:
					break
				s -= 1
print(s)


(a, b, c, d) = map(int, input().split())
A = [0] * a
for i in range(len(A)):
	A[i] = [0] * b
for i in range(c):
	(per1, per2) = map(int, input().split())
	A[per1 - 1][per2 - 1] = 1
ans = 0
for i in range(a):
	for j in range(b):
		for k in range(i, a):
			for t in range(j, b):
				cou = 0
				for s in range(i, k + 1):
					for m in range(j, t + 1):
						if A[s][m] == 1:
							cou += 1
				if cou >= d:
					ans += 1
print(ans)


(r, c, n, k) = map(int, input().split())
V = [list(map(int, input().split())) for _ in range(n)]
G = [[0 for _ in range(c)] for _ in range(r)]
for i in range(n):
	G[V[i][0] - 1][V[i][1] - 1] = 1
T = [[0 for _ in range(c)] for _ in range(r)]
T[0][0] = G[0][0]
for i in range(1, r):
	T[i][0] = G[i][0]
for i in range(r):
	for j in range(1, c):
		T[i][j] = T[i][j - 1] + G[i][j]
for i in range(1, r):
	for j in range(c):
		T[i][j] += T[i - 1][j]
nb = 0
for x1 in range(c):
	for x2 in range(x1, c):
		for y1 in range(r):
			for y2 in range(y1, r):
				s = T[y2][x2]
				if x1 > 0:
					s -= T[y2][x1 - 1]
				if y1 > 0:
					s -= T[y1 - 1][x2]
				if x1 > 0 and y1 > 0:
					s += T[y1 - 1][x1 - 1]
				if s >= k:
					nb += 1
print(nb)


(r, c, n, k) = map(int, input().split())
xy = [list(map(int, input().split())) for i in range(n)]
field = [[0] * c for i in range(r)]
for i in range(n):
	field[xy[i][0] - 1][xy[i][1] - 1] = 1
num = 0
for i in range(r):
	for j in range(c):
		for i2 in range(i, r):
			for j2 in range(j, c):
				num2 = 0
				for i3 in range(i, i2 + 1):
					for j3 in range(j, j2 + 1):
						if field[i3][j3] == 1:
							num2 += 1
				if num2 >= k:
					num += 1
print(num)


(R, C, N, K) = map(int, input().split())
v = []
for i in range(N):
	v.append(tuple(map(int, input().split())))
ans = 0
for sr in range(1, R + 1):
	for sc in range(1, C + 1):
		for er in range(sr, R + 1):
			for ec in range(sc, C + 1):
				cnt = 0
				for (x, y) in v:
					if sr <= x <= er and sc <= y <= ec:
						cnt += 1
				if cnt >= K:
					ans += 1
print(ans)


def check(x1, y1, x2, y2):
	global dp
	cnt = 0
	for i in range(x2, x1 + 1):
		for j in range(y2, y1 + 1):
			cnt += dp[i][j]
	return cnt
(r, c, n, k) = map(int, input().split())
dp = [[0] * c for i in range(r)]
for i in range(n):
	(a, b) = map(int, input().split())
	dp[a - 1][b - 1] = 1
answer = 0
for x1 in range(r):
	for y1 in range(c):
		for x2 in range(x1 + 1):
			for y2 in range(y1 + 1):
				cnt = check(x1, y1, x2, y2)
				if cnt >= k:
					answer += 1
print(answer)


import time
a = []
(r, c, n, k) = (int(i) for i in input().split())
for i in range(n):
	a.append([int(i) - 1 for i in input().split()])
start = time.time()
ans = 0
for x1 in range(r):
	for y1 in range(c):
		for x0 in range(x1 + 1):
			for y0 in range(y1 + 1):
				now = 0
				for i in range(n):
					if a[i][0] >= x0 and a[i][0] <= x1 and (a[i][1] >= y0) and (a[i][1] <= y1):
						now += 1
				if now >= k:
					ans += 1
print(ans)
finish = time.time()


def main():
	from itertools import combinations
	(r, c, n, k) = map(int, input().split())
	r += 1
	c += 1
	l = [[0] * c for _ in range(r)]
	for _ in range(n):
		(y, x) = map(int, input().split())
		for i in range(y, r):
			row = l[i]
			for j in range(x, c):
				row[j] += 1
	print(sum((l[y][x] + l[i][j] - l[y][j] - l[i][x] >= k for (i, y) in combinations(range(r), 2) for (j, x) in combinations(range(c), 2))))
main()


read = lambda : map(int, input().split())
(r, c, n, k) = read()
a = [[0] * (c + 1) for i in range(r + 1)]
for i in range(n):
	(x, y) = read()
	a[x][y] = 1
d = [[0] * (c + 1) for i in range(r + 1)]
for i in range(1, r + 1):
	for j in range(1, c + 1):
		if a[i][j]:
			d[i][j] += 1
		if i == j == 0:
			continue
		p1 = d[i - 1][j] if i else 0
		p2 = d[i][j - 1] if j else 0
		p3 = d[i - 1][j - 1] if i and j else 0
		d[i][j] += p1 + p2 - p3
cnt = 0
for x1 in range(r + 1):
	for y1 in range(c + 1):
		for x2 in range(x1 + 1, r + 1):
			for y2 in range(y1 + 1, c + 1):
				cur = d[x2][y2] - d[x2][y1] - d[x1][y2] + d[x1][y1]
				if cur >= k:
					cnt += 1
print(cnt)


def cnt(x1, y1, x2, y2):
	ans = 0
	for i in range(y2, y1 + 1):
		for j in range(x1, x2 + 1):
			if lst[i][j] == 1:
				ans += 1
	return ans
(h, w, n, kk) = list(map(int, input().split()))
anss = 0
lst = [[0] * 20 for i in range(20)]
for i in range(n):
	(x, y) = list(map(int, input().split()))
	lst[x - 1][y - 1] = 1
for i in range(h):
	for j in range(w):
		for k in range(h):
			for z in range(w):
				if cnt(j, i, z, k) >= kk:
					anss += 1
print(anss)


(r, c, n, k) = map(int, input().split())
a = [[0 for i in range(0, c)] for j in range(0, r)]
for i in range(0, n):
	(x, y) = map(int, input().split())
	x = x - 1
	y = y - 1
	a[x][y] = 1
ans = 0
for i in range(0, r):
	for j in range(0, c):
		for u in range(i, r):
			for v in range(j, c):
				t = 0
				for x in range(i, u + 1):
					for y in range(j, v + 1):
						t += a[x][y]
				if t >= k:
					ans = ans + 1
print(ans)


(w, h, v, n) = list(map(int, input().split()))
V = [[False] * h for _ in range(w)]
for _ in range(v):
	(x, y) = list(map(int, input().split()))
	V[x - 1][y - 1] = True

def calc(a, b, c, d):
	s = 0
	for x in range(a, c + 1):
		for y in range(b, d + 1):
			s += V[x][y]
			if s >= n:
				return s
	return s
C = 0
for x1 in range(w):
	for y1 in range(h):
		for x2 in range(x1, w):
			for y2 in range(y1, h):
				if calc(x1, y1, x2, y2) >= n:
					C += 1
print(C)


(r, c, n, p) = map(int, input().split())
resp = 0
m = []
for i in range(r):
	aux = []
	for j in range(c):
		aux.append(False)
	m.append(aux[:])
for i in range(n):
	(x, y) = map(int, input().split())
	m[x - 1][y - 1] = True
for i in range(r):
	for j in range(c):
		for a in range(r, i, -1):
			for b in range(c, j, -1):
				cont = 0
				for k in range(i, a):
					for l in range(j, b):
						if m[k][l]:
							cont += 1
				if cont >= p:
					resp += 1
print(resp)


f = lambda : map(int, input().split())
(r, c, n, k) = f()
t = [list(f()) for i in range(n)]
s = 0
for i in range(1, r + 1):
	for j in range(i, r + 1):
		for u in range(1, c + 1):
			for v in range(u, c + 1):
				s += sum([i <= x <= j and u <= y <= v for (x, y) in t]) >= k
print(s)


(string, column, cnt, mincnt) = map(int, input().split())
maps = [['*' for i in range(column)] for j in range(string)]
for i in range(cnt):
	(a, b) = map(int, input().split())
	maps[a - 1][b - 1] = '#'
ans = 0
for i in range(string):
	for j in range(column):
		for i1 in range(i, string):
			for j1 in range(j, column):
				num = 0
				for s in range(i, i1 + 1):
					for c in range(j, j1 + 1):
						if maps[s][c] == '#':
							num += 1
				if num >= mincnt:
					ans += 1
print(ans)


def count(a, b, c, d):
	return sum([arr[i][j] for i in range(a, c + 1) for j in range(b, d + 1)])

def solve(r, c, n, m):
	ans = 0
	for i in range(1, r + 1):
		for j in range(1, c + 1):
			for k in range(i, r + 1):
				for l in range(j, c + 1):
					x = count(i, j, k, l)
					if x >= m:
						ans += 1
	return ans
(r, c, n, k) = list(map(int, input().split()))
arr = [[0 for i in range(20)] for j in range(20)]
for i in range(n):
	(x, y) = list(map(int, input().split()))
	arr[x][y] = 1
print(solve(r, c, n, k))


(r, c, n, k) = map(int, input().split())
a = []
q = 0
for i in range(r):
	a.append([0] * c)
for i in range(n):
	(x, y) = map(int, input().split())
	a[x - 1][y - 1] = 1
for i in range(r):
	for j in range(c):
		for m in range(r - i + 1):
			for p in range(c - j + 1):
				s = 0
				for d in range(i, i + m):
					for b in range(j, j + p):
						s += a[d][b]
				if s >= k:
					q += 1
print(q)


(r, c, n, k) = map(int, input().split())
G = [[0] * c for i in range(0, r)]
for i in range(0, n):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	G[a][b] = True
ans = 0
for x in range(0, r):
	for y in range(0, c):
		for y1 in range(y + 1, c + 1):
			for x1 in range(x + 1, r + 1):
				num = 0
				for cl in range(y, y1):
					for rw in range(x, x1):
						if G[rw][cl]:
							num += 1
				if num >= k:
					ans += 1
print(ans)


(r, c, n, k) = map(int, input().split())
A = [[0] * c for i in range(r)]
for i in range(n):
	(a, b) = map(int, input().split())
	A[a - 1][b - 1] = 1
f = 0
g = 0
ans = 0
for i in range(r):
	for j in range(c):
		for i2 in range(r - i):
			for j2 in range(c - j):
				cnt = 0
				for i3 in range(i, i + i2 + 1):
					for j3 in range(j, j + j2 + 1):
						cnt += int(A[i3][j3] == 1)
				if cnt >= k:
					ans += 1
print(ans)


(r, c, n, k) = list(map(int, input().split()))
A = [2] * n
for i in range(n):
	A[i] = list(map(int, input().split()))
answer = 0
for i1 in range(1, r + 1):
	for j1 in range(1, c + 1):
		for i2 in range(i1, r + 1):
			for j2 in range(j1, c + 1):
				t = 0
				for i in range(n):
					if i1 <= A[i][0] <= i2 and j1 <= A[i][1] <= j2:
						t += 1
				answer += t >= k
print(answer)


readInts = lambda : list(map(int, input().split()))
pos = []
(r, c, n, k) = readInts()
for i in range(n):
	(x, y) = readInts()
	pos.append([x - 1, y - 1])
ret = 0
for i in range(r):
	for j in range(c):
		for ii in range(i, r):
			for jj in range(j, c):
				cnt = 0
				for it in range(n):
					(x, y) = pos[it]
					if x >= i and x <= ii and (y >= j) and (y <= jj):
						cnt += 1
				if cnt >= k:
					ret += 1
print(ret)


(r, c, n, k) = list(map(int, input().split()))
board = [[0 for col in range(c)] for row in range(r)]
for i in range(n):
	(x, y) = [int(x) - 1 for x in input().split()]
	board[x][y] = 1
photos = 0
for x1 in range(r):
	for y1 in range(c):
		for x2 in range(x1, r):
			for y2 in range(y1, c):
				s = 0
				for row in range(x1, x2 + 1):
					s += sum(board[row][y1:y2 + 1])
				if s >= k:
					photos += 1
print(photos)


(r, c, n, k) = map(int, input().split())
d = [[0 for j in range(c + 1)] for i in range(r + 1)]
for i in range(n):
	(x, y) = map(int, input().split())
	d[x][y] = 1
for i in range(1, r + 1):
	for j in range(1, c + 1):
		d[i][j] = d[i][j] + d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1]
a = 0
for i in range(1, r + 1):
	for j in range(1, c + 1):
		for x in range(i, r + 1):
			for y in range(j, c + 1):
				if d[x][y] - d[x][j - 1] - d[i - 1][y] + d[i - 1][j - 1] >= k:
					a += 1
print(a)


import collections
import math
(r, c, n, k) = map(int, input().split())
T = []
ans = 0
for i in range(n):
	(x, y) = map(int, input().split())
	T.append((x, y))
for ri in range(1, r + 1):
	for rj in range(ri, r + 1):
		for ci in range(1, c + 1):
			for cj in range(ci, c + 1):
				t = 0
				for i in range(len(T)):
					if ri <= T[i][0] <= rj and ci <= T[i][1] <= cj:
						t += 1
				if t >= k:
					ans += 1
print(ans)


(r, c, n, k) = input().split()
(r, c, n, k) = (int(r), int(c), int(n), int(k))
violas = []
for _ in range(n):
	(x, y) = input().split()
	(x, y) = (int(x) - 1, int(y) - 1)
	violas.append((y, x))

def count_violas(x1, y1, x2, y2):
	global violas
	s = 0
	for (x, y) in violas:
		if x >= x1 and x <= x2 and (y >= y1) and (y <= y2):
			s += 1
	return s
ans = 0
for x1 in range(c):
	for y1 in range(r):
		for x2 in range(x1, c):
			for y2 in range(y1, r):
				if count_violas(x1, y1, x2, y2) >= k:
					ans += 1
print(ans)


(r, c, n, k) = map(int, input().split())
a = [[0] * 20 for i in range(20)]
for i in range(n):
	(x, y) = map(int, input().split())
	a[x - 1][y - 1] = 1
ans = 0
for i in range(r):
	for j in range(c):
		for i2 in range(i, r):
			for j2 in range(j, c):
				num = 0
				for i3 in range(i, i2 + 1):
					for j3 in range(j, j2 + 1):
						if a[i3][j3]:
							num += 1
				if num >= k:
					ans += 1
print(ans)


(b, a, n, k) = map(int, input().split())
data = [[0 for i in range(a)] for j in range(b)]
for i in range(n):
	(xi, yi) = map(int, input().split())
	xi -= 1
	yi -= 1
	data[xi][yi] = 1
answer = 0
for i in range(b):
	for j in range(a):
		for x in range(i, b):
			for y in range(j, a):
				counter = 0
				for x1 in range(min(i, x), max(i, x) + 1):
					for y1 in range(min(j, y), max(j, y) + 1):
						counter += data[x1][y1]
				if counter >= k:
					answer += 1
print(answer)


(r, c, n, k) = list(map(int, input().split()))
alt = []
count = 0
for i in range(n):
	(a, b) = list(map(int, input().split()))
	alt.append([a - 1, b - 1])
for x1 in range(r):
	for x2 in range(x1 + 1):
		for y1 in range(c):
			for y2 in range(y1 + 1):
				d = 0
				for i in range(n):
					if alt[i][0] <= x1 and alt[i][0] >= x2 and (alt[i][1] <= y1) and (alt[i][1] >= y2):
						d += 1
				if d >= k:
					count += 1
print(count)


from collections import defaultdict as Matrix
from itertools import product
(r, c, n, k) = map(int, input().split())
dp = Matrix(int)
for _ in range(n):
	(x, y) = [int(cc) - 1 for cc in input().split()]
	for (x0, y0) in product(range(x + 1), range(y + 1)):
		for (x1, y1) in product(range(x, r), range(y, c)):
			if x0 <= x <= x1 and y0 <= y <= y1:
				dp[x0, y0, x1, y1] += 1
ans = sum((1 for v in dp.values() if v >= k))
print(ans)


(r, c, n, k) = map(int, input().split())
(g, v) = ([[False] * c for i in range(r)], 0)
for i in range(n):
	(x, y) = map(int, input().split())
	g[x - 1][y - 1] = True
for a in range(r):
	for b in range(c):
		for e in range(a, r):
			for f in range(b, c):
				x = sum((g[i][j] for i in range(a, e + 1) for j in range(b, f + 1)))
				if x >= k:
					v += 1
print(v)


(r, c, n, k) = map(int, input().split(' '))
p = []

def findIn(z, x, y, s):
	global n
	ret = 0
	for i in range(n):
		if z <= p[i][0] and y >= p[i][0] and (x <= p[i][1]) and (s >= p[i][1]):
			ret = ret + 1
	return ret
for i in range(n):
	(x, y) = map(int, input().split(' '))
	p.append((x, y))
ans = 0
for z in range(1, r + 1):
	for x in range(1, c + 1):
		for y in range(z, r + 1):
			for s in range(x, c + 1):
				if findIn(z, x, y, s) >= k:
					ans = ans + 1
print(ans)


(r, c, n, k) = map(int, input().split())
M = [['*'] * c for i in range(r)]
for i in range(n):
	(x, y) = map(int, input().split())
	M[x - 1][y - 1] = '#'

def contain(M, k, x1, y1, x2, y2):
	for i in range(x1, x2 + 1):
		for j in range(y1, y2 + 1):
			if M[i][j] == '#':
				k -= 1
	return k <= 0
ans = 0
for x1 in range(r):
	for y1 in range(c):
		for x2 in range(x1, r):
			for y2 in range(y1, c):
				if contain(M, k, x1, y1, x2, y2):
					ans += 1
print(ans)


(r, c, n, k) = map(int, input().split())
data = [[False for i in range(c)] for j in range(r)]
for i in range(n):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	data[x][y] = True
ans = 0
for a in range(r + 1):
	for b in range(c + 1):
		for e in range(r):
			for d in range(c):
				cnt = 0
				flag = False
				for i in range(a):
					for j in range(b):
						if 0 <= e + i < r and 0 <= d + j < c:
							if data[e + i][d + j]:
								cnt += 1
						else:
							flag = True
							break
					if flag:
						break
				if flag:
					continue
				if cnt >= k:
					ans += 1
print(ans)


L = lambda : [*map(int, input().split())]
(r, c, n, k) = L()
A = [L() for _ in range(n)]
print(sum((sum((a <= x <= b and f <= y <= g for (x, y) in A)) >= k for a in range(1, r + 1) for b in range(a, r + 1) for f in range(1, c + 1) for g in range(f, c + 1))))


(r, c, n, k) = map(int, input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
ans = 0
for x1 in range(1, r + 1):
	for x2 in range(x1, r + 1):
		for y1 in range(1, c + 1):
			for y2 in range(y1, c + 1):
				if len([1 for (x, y) in a if x1 <= x <= x2 and y1 <= y <= y2]) >= k:
					ans += 1
print(ans)


(r, c, n, k) = [int(x) for x in input().split()]
(min_x, min_y, max_x, max_y) = (r, c, 1, 1)
alts = []
for i in range(0, n):
	(x, y) = [int(i) for i in input().split()]
	alts.append((x, y))
photo_count = 0
for x in range(1, r + 1):
	for y in range(1, c + 1):
		for w in range(1, r - (x - 1) + 1):
			for h in range(1, c - (y - 1) + 1):
				alt_count = 0
				for alt in alts:
					if x <= alt[0] <= x + w - 1 and y <= alt[1] <= y + h - 1:
						alt_count += 1
					if alt_count >= k:
						photo_count += 1
						break
print(photo_count)


s = input()
S = s.split()
x = int(S[0])
y = int(S[1])
n = int(S[2])
k = int(S[3])
a = [['*' for i in range(x)] for j in range(y)]
for i in range(n):
	alt = input()
	ALT = alt.split()
	a[int(ALT[1]) - 1][int(ALT[0]) - 1] = '#'
answer = 0
for x1 in range(x):
	for y1 in range(y):
		for x2 in range(x1, x):
			for y2 in range(y1, y):
				count = 0
				for i in range(x1, x2 + 1):
					for j in range(y1, y2 + 1):
						if a[j][i] == '#':
							count += 1
				if count >= k:
					answer += 1
print(answer)


def count(orchestra, initial, final):
	num = 0
	for i in range(initial[0], final[0] + 1):
		for j in range(initial[1], final[1] + 1):
			if orchestra[i][j] == 1:
				num += 1
	return num

def getNumber(orchestra, initial, minimum):
	num = 0
	for i in range(initial[0], r):
		for j in range(initial[1], c):
			final = [i, j]
			counter = count(orchestra, initial, final)
			if counter >= k:
				num += 1
	if initial[0] == len(orchestra):
		return num
	if initial[1] == len(orchestra[0]) - 1:
		initial[0] += 1
		initial[1] = 0
	else:
		initial[1] += 1
	return num + getNumber(orchestra, initial, minimum)
args = list(map(int, input().split()))
r = args[0]
c = args[1]
n = args[2]
k = args[3]
positions = []
for i in range(n):
	x = list(map(int, input().split()))
	positions.append([x[0], x[1]])
orchestra = [[0] * c for i in range(r)]
for i in positions:
	orchestra[i[0] - 1][i[1] - 1] = 1
print(getNumber(orchestra, [0, 0], k))


tmp = input().split(' ')
r = int(tmp[0])
c = int(tmp[1])
n = int(tmp[2])
k = int(tmp[3])
tab = [[0]]
for j in range(1, c + 1):
	tab[0].append(0)
for i in range(1, r + 1):
	tab.append([0])
	for j in range(1, c + 1):
		tab[i].append(0)
for i in range(0, n):
	tmp = input().split(' ')
	tab[int(tmp[0])][int(tmp[1])] = 1
pre = tab
for i in range(1, r + 1):
	for j in range(1, c + 1):
		pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + tab[i][j]
wynik = 0
for i in range(1, r + 1):
	for j in range(1, c + 1):
		for ii in range(i, r + 1):
			for jj in range(j, c + 1):
				if tab[ii][jj] - tab[i - 1][jj] - tab[ii][j - 1] + tab[i - 1][j - 1] >= k:
					wynik = wynik + 1
print(wynik)


dhuang = 0
(a, b, c, d) = list(map(int, input().split(' ')))
huang = [['*'] * b for _ in range(a)]
for i in range(c):
	(x, y) = list(map(int, input().split(' ')))
	huang[x - 1][y - 1] = '#'
for i in range(a):
	for j in range(b):
		for k in range(i, a):
			for l in range(j, b):
				ct = 0
				for m in range(i, k + 1):
					for n in range(j, l + 1):
						if huang[m][n] == '#':
							ct += 1
				if ct >= d:
					dhuang += 1
print(dhuang)


from collections import Counter
(r, c, n, k) = map(int, input().split())
dp = Counter()
for _ in range(n):
	(x, y) = [int(cc) - 1 for cc in input().split()]
	for x0 in range(x + 1):
		for y0 in range(y + 1):
			for x1 in range(x, r):
				for y1 in range(y, c):
					dp[x0, y0, x1, y1] += 1
ans = sum((1 for v in dp.values() if v >= k))
print(ans)


(r, c, n, k) = [int(x) for x in input().split()]
mus = [[0 for j in range(c)] for i in range(r)]
for t in range(n):
	(x, y) = [int(s) - 1 for s in input().split()]
	mus[x][y] = 1
ans = 0
for i1 in range(r):
	for i2 in range(i1, r):
		for j1 in range(c):
			for j2 in range(j1, c):
				S = 0
				for x in range(i1, i2 + 1):
					for y in range(j1, j2 + 1):
						S += mus[x][y]
				if S >= k:
					ans += 1
print(ans)


import io
import sys
import time
import random
(r, c, n, k) = map(int, input().split())
data = [[0 for i in range(c)] for j in range(r)]
for i in range(n):
	(x, y) = map(int, input().split())
	data[x - 1][y - 1] = 1
nviolists = [[0 for i in range(c)] for j in range(r)]
for r1 in range(r):
	count = 0
	for c1 in range(c):
		count += data[r1][c1]
		nviolists[r1][c1] = (nviolists[r1 - 1][c1] if r1 > 0 else 0) + count
count = 0
for r1 in range(r):
	for r2 in range(r1, r):
		for c1 in range(c):
			for c2 in range(c1, c):
				vcount = nviolists[r2][c2] - (nviolists[r1 - 1][c2] if r1 > 0 else 0) - (nviolists[r2][c1 - 1] if c1 > 0 else 0) + (nviolists[r1 - 1][c1 - 1] if r1 * c1 > 0 else 0)
				if vcount >= k:
					count += 1
print(count)


def read_ints():
	return map(int, input().split())
(r, c, n, k) = read_ints()
s = [[False] * (c + 1) for _ in range(r + 1)]
for _ in range(n):
	(x, y) = read_ints()
	assert x <= r, x
	assert y <= c, y
	s[x][y] = True
ss = [[0] * (c + 1) for _ in range(r + 1)]
for y in range(1, r + 1):
	for x in range(1, c + 1):
		ss[y][x] = ss[y - 1][x] + ss[y][x - 1] - ss[y - 1][x - 1] + int(s[y][x])

def count(lx, ly, rx, ry, ss):
	assert 0 < lx <= c, lx
	assert 0 < rx <= c, rx
	assert 0 < ly <= r, ly
	assert 0 < ry <= r, ry
	return ss[ry][rx] - ss[ly - 1][rx] - ss[ry][lx - 1] + ss[ly - 1][lx - 1]
ccc = 0
for ly in range(1, r + 1):
	for lx in range(1, c + 1):
		for ry in range(ly, r + 1):
			for rx in range(lx, c + 1):
				if count(lx, ly, rx, ry, ss) >= k:
					ccc += 1
print(ccc)


def count(orchestra, x1, y1, x2, y2):
	rv = 0
	for i in range(x1, x2 + 1):
		for j in range(y1, y2 + 1):
			if orchestra[i][j] == 1:
				rv += 1
	return rv

def doit(r, c, n, k, pos):
	orchestra = [[0 for x in range(c)] for x in range(r)]
	for i in pos:
		orchestra[i[0] - 1][i[1] - 1] = 1
	rv = 0
	for i1 in range(r):
		for i2 in range(c):
			for i3 in range(i1, r):
				for i4 in range(i2, c):
					if count(orchestra, i1, i2, i3, i4) >= k:
						rv += 1
	return rv
args = list(map(int, input().split()))
r = args[0]
c = args[1]
n = args[2]
k = args[3]
pos = []
for i in range(n):
	z = list(map(int, input().split()))
	x = z[0]
	y = z[1]
	pos.append([x, y])
print(doit(r, c, n, k, pos))


(r, c, n, k) = map(int, input().split())
g = set([tuple(map(int, input().split())) for _ in range(n)])
ret = 0
for i in range(r):
	for j in range(c):
		for l in range(1, r - i + 1):
			for w in range(1, c - j + 1):
				count = 0
				for a in range(i, i + l):
					for b in range(j, j + w):
						if (a + 1, b + 1) in g:
							count += 1
				if count >= k:
					ret += 1
print(ret)


(r, c, n, k) = list(map(int, input().split()))
p = []
for i in range(r):
	p.append([0] * c)
for i in range(n):
	(x, y) = list(map(int, input().split()))
	p[x - 1][y - 1] = 1
ans = 0
for i in range(r):
	for t in range(c):
		for e in range(r):
			for g in range(c):
				col = 0
				for h in range(i, e + 1):
					for f in range(t, g + 1):
						col += p[h][f]
				if col >= k:
					ans += 1
print(ans)


(r, c, n, k) = map(int, input().split())
s = [[0] * c for i in range(r)]
for i in range(n):
	(x, y) = map(int, input().split())
	s[x - 1][y - 1] = 1
res = 0
for br in range(r):
	for bc in range(c):
		for er in range(br, r):
			for ec in range(bc, c):
				counter = 0
				for i in range(br, er + 1):
					for j in range(bc, ec + 1):
						if s[i][j] == 1:
							counter += 1
				if counter >= k:
					res += 1
print(res)


(r, c, n, k) = map(int, input().split())
violas = set([tuple(map(int, input().split())) for i in range(n)])
ans = 0
for i in range(r):
	for j in range(c):
		for l in range(1, r - i + 1):
			for w in range(1, c - j + 1):
				ctr = 0
				for a in range(i, i + l):
					for b in range(j, j + w):
						if (a + 1, b + 1) in violas:
							ctr += 1
				if ctr >= k:
					ans += 1
print(ans)


(r, c, n, k) = [int(i) for i in input().split()]
a = [[0] * r for i in range(c)]
for i in range(n):
	(x, y) = [int(i) for i in input().split()]
	a[y - 1][x - 1] = 1
ct1 = 0
for i in range(c):
	for j in range(r):
		for s in range(i + 1, c + 1):
			for t in range(j + 1, r + 1):
				ct = 0
				for u in range(i, s):
					for v in range(j, t):
						if a[u][v] == 1:
							ct += 1
				if ct >= k:
					ct1 += 1
print(ct1)