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 ≤ 3000, 1 ≤ k ≤ min(n, 10)) — 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 xi and yi (1 ≤ xi ≤ r, 1 ≤ yi ≤ 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.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Iterator;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.Comparator;
import java.io.InputStream;
import java.util.function.IntFunction;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            FOrchestra solver = new FOrchestra();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class FOrchestra {
        Debug debug = new Debug(true);
        long sum;

        void contribute(Point pt, int sign) {
            sum += sign * pt.weight * pt.target.y;
        }

        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.ri();
            int m = in.ri();
            int ptCnt = in.ri();
            int k = in.ri();
            Point[] pts = new Point[ptCnt];
            for (int i = 0; i < ptCnt; i++) {
                pts[i] = new Point();
                pts[i].x = in.ri() - 1;
                pts[i].y = in.ri() - 1;
            }
            Arrays.sort(pts, Comparator.comparingInt(x -> x.y));
            Point dummyHead = new Point();
            Point dummyEnd = new Point();
            dummyHead.y = -1;
            dummyEnd.y = m;
            Point[] ptsSortedByX = pts.clone();
            Arrays.sort(ptsSortedByX, Comparator.comparingInt(x -> x.x));
            long ans = 0;
            for (int low = 0; low < n; low++) {
                long contrib = 0;
                sum = 0;
                Point head = dummyHead;
                Point end = dummyEnd;
                head.next = end;
                end.prev = head;
                end.next = end;
                head.weight = end.weight = 0;
                for (Point pt : pts) {
                    pt.next = pt.prev = pt.target = null;
                    pt.weight = 0;
                    if (pt.x < low) {
                        continue;
                    }
                    pt.prev = end.prev;
                    pt.prev.next = pt;
                    pt.next = end;
                    end.prev = pt;
                }
                head.target = head;
                for (int i = 1; i < k; i++) {
                    head.target = head.target.next;
                }
                for (Point node = head.next; ; node = node.next) {
                    node.target = node.prev.target.next;
                    node.weight = node.y - node.prev.y;
                    if (node == end) {
                        node.weight--;
                    }
                    contribute(node, 1);
                    if (node == end) {
                        break;
                    }
                }
                SimplifiedDeque<Point> dq = new Range2DequeAdapter<>(i -> ptsSortedByX[i], 0, ptsSortedByX.length - 1);
                for (int high = n - 1; high >= low; high--) {
                    while (!dq.isEmpty() && dq.peekLast().x > high) {
                        Point pt = dq.removeLast();
                        if (k > 1) {
                            for (Point node = pt.prev; node != null; node = node.prev) {
                                Point prevEnd = node.target;
                                contribute(node, -1);
                                if (prevEnd == pt) {
                                    break;
                                }
                            }
                        }
                        contribute(pt.next, -1);
                        contribute(pt, -1);
                        if (k > 1) {
                            for (Point node = pt.prev; node != null; node = node.prev) {
                                Point prevEnd = node.target;
                                node.target = prevEnd.next;
                                contribute(node, 1);
                                if (prevEnd == pt) {
                                    break;
                                }
                            }
                        }
                        pt.next.weight += pt.weight;
                        contribute(pt.next, 1);
                        pt.next.prev = pt.prev;
                        pt.prev.next = pt.next;
                    }
                    contrib += (long) m * m - sum;
                    debug.debug("low", low);
                    debug.debug("high", high);
                    debug.debug("contrib", m * m - sum);
                }
                ans += contrib;
            }
            out.println(ans);
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 1 << 13;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(long c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(String c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println(long c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append(System.lineSeparator());
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static interface SimplifiedStack<T> extends Iterable<T> {
        boolean isEmpty();

        T peekLast();

        T removeLast();

    }

    static interface SimplifiedDeque<T> extends SimplifiedStack<T> {
    }

    static class Debug {
        private boolean offline;
        private PrintStream out = System.err;

        public Debug(boolean enable) {
            offline = enable && System.getSecurityManager() == null;
        }

        public Debug debug(String name, int x) {
            if (offline) {
                debug(name, "" + x);
            }
            return this;
        }

        public Debug debug(String name, long x) {
            if (offline) {
                debug(name, "" + x);
            }
            return this;
        }

        public Debug debug(String name, String x) {
            if (offline) {
                out.printf("%s=%s", name, x);
                out.println();
            }
            return this;
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int ri() {
            return readInt();
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }

    static class Range2DequeAdapter<T> implements SimplifiedDeque<T> {
        IntFunction<T> data;
        int l;
        int r;

        public Range2DequeAdapter(IntFunction<T> data, int l, int r) {
            this.data = data;
            this.l = l;
            this.r = r;
        }

        public boolean isEmpty() {
            return l > r;
        }

        public T peekLast() {
            return data.apply(r);
        }

        public T removeLast() {
            return data.apply(r--);
        }

        public Iterator<T> iterator() {
            return new Iterator<T>() {
                int iter = l;


                public boolean hasNext() {
                    return iter <= r;
                }


                public T next() {
                    return data.apply(iter++);
                }
            };
        }

    }

    static class Point {
        int x;
        int y;
        long weight;
        Point prev;
        Point next;
        Point target;

        public String toString() {
            return "(" + x + "," + y + ")";
        }

    }
}

