Tinted Glass Window

Time limit1sMemory limit256 MB

Summary

N overlapping rectangles each add an integer tint to the area they cover, and you must find the total area whose summed tint is at least T.

Level: Medium6 of 10
Topics: Prefix sum, Sorting, Geometry
Solved: No attempts yet

Problem

You place N rectangular grey-tinted glass panes to build a stained glass window. Each pane adds an integer tint-factor. Where panes overlap, the tint-factors add.

Each pane is axis-aligned. Find the total area whose tint-factor is at least T.

Input

The first line is N (1 ≤ N ≤ 1000). The second line is T (1 ≤ T ≤ 1 000 000 000). Each of the next N lines has five integers xl yt xr yb ti. The top-left corner is (xl, yt), the bottom-right is (xr, yb), and ti is the pane tint-factor. You have 1 ≤ ti ≤ 1 000 000, 0 ≤ xl < xr ≤ K, 0 < yt < yb ≤ K, and K ≤ 1 000 000 000.

Output

Print the total area with tint-factor at least T. Every answer is below 2^64.

Examples2

Example 1

Input

4
3
11 11 20 15 1
13 8 14 17 2
17 8 18 17 1
12 12 19 13 1

Expected output

Example 2
Input
```
1
1
0 1 2 3 5
```
Expected output
```
4
```