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: interview

Starter code:

Solutions:
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)


#they are all inclusive
R, C, N, K = list(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)


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)

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())
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 = 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 = [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)


def check(x1, y1, x2, y2):
    nonlocal dp
    cnt = 0
    for i in range(x2, x1 + 1):
        for j in range(y2, y1 + 1):
            cnt += dp[i][j]
    return cnt


#n = int(input())
r, c, n, k = list(map(int, input().split()))
#s = list(map(int, input().split()))
dp = [[0] * c for i in range(r)]
for i in range(n):
    a, b = list(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)
                #print(cnt, x1, y1, x2, y2)
                if cnt >= k:
                    answer += 1
print(answer)


r, c, n, k = list(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 = 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):
                        #print(i3, j3)
                        cnt += int(A[i3][j3] == 1)
                if cnt >= k:
                    ans += 1
print(ans)

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)

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 = list(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)


read = lambda: list(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)


r, c, n, k = list(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 = list(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)


#!/usr/bin/env python3
# -*- coding: utf-8 -*-

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()
#print(finish - start)


# You lost the game.
r,c,n,k = list(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 = list(map(int, input().split()))
data = [[False for i in range(c)] for j in range(r)]
for i in range(n):
	x, y = list(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)




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)                
    


import io
import sys
import time
import random
#~ start = time.clock()
#~ test = '''2 2 1 1
#~ 1 2'''
#~ test = '''3 2 3 3
#~ 1 1
#~ 3 1
#~ 2 2'''
#~ test = '''3 2 3 2
#~ 1 1
#~ 3 1
#~ 2 2'''

#~ sys.stdin = io.StringIO(test)

r,c,n,k = list(map(int,input().split())) # row column number-of-violists
data = [ [0 for i in range(c)] for j in range(r) ]
#~ print(r,c,n,k)

for i in range(n):
   x,y = list(map(int,input().split())) # row column
   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
      #~ print(r1,c1,nviolists[r1][c1],nviolists[r1][c1-1])
      #~ print(nviolists)

count = 0
for r1 in range(r):
   for r2 in range(r1,r):
      for c1 in range(c):
         for c2 in range(c1,c):
            # between (r1,c1) and (r2,c2)
            
            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:
               #~ print( (r1,c1), (r2,c2) )
               count +=1 
               

print(count)         
#~ dur = time.clock()-start
#~ print("Time:",dur)


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):
    nonlocal 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)

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))


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)

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)


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))