Transparent Mosaic

Interview

Time limit2sMemory limit128 MB

Summary

Given N rectangular paper sheets on a 100x100 grid, count cells covered by more than M sheets.

Level: Easy3 of 10
Topics: Array, Simulation, Brute force
Solved: No attempts yet

Problem

Sejun has a mosaic made of 100×100 small 1×1 pictures. One day, he disliked some parts of the mosaic and began covering them with N opaque sheets of paper.

A cell does not necessarily become invisible just because it is covered by paper. If a cell has at most M sheets on top of it, the picture in that cell is still visible. Only cells covered by more than M sheets are invisible.

Each sheet is given by the coordinates of its lower-left corner and upper-right corner. The covered area includes both corner coordinates. For example, covering from (1, 1) to (2, 2) covers four cells: (1, 1), (1, 2), (2, 1), and (2, 2).

Find the number of invisible cells in the 100×100 mosaic.

Input

The first line contains integers N and M. Both N and M are between 0 and 50, inclusive.

Each of the next N lines describes one sheet of paper. A line contains the x and y coordinates of the lower-left corner, followed by the x and y coordinates of the upper-right corner. Every coordinate is a positive integer not greater than 100.

Output

Print the number of invisible cells on the first line.

Examples1

Example 1

Input

3 1
21 21 80 80
41 41 60 60
71 71 90 90

Expected output