Brave Boasting

Time limit1sMemory limit1024 MB

Summary

Given n axis-aligned rectangles and a segment of length l, find the maximum number of rectangles one segment of length l can intersect.

Level: Medium7 of 10
Topics: Geometry, Brute force
Solved: No attempts yet

Problem

Winter is coming. Gas heating keeps getting more expensive, so firewood is the alternative. Mirko and Slavko split logs and prepare for winter. After an hour of work, they take a short break and sit in silence, drinking water. To break the boredom, Mirko says:

"Slavko, I can split three logs with a single swing of an axe."

Slavko raises his eyebrows, pouts, and replies: "Ha, I think I could manage at least six or seven."

You are watching this exchange from the side. You would love to say: "Guys, that is weak. I can split exactly c logs with a single swing of an axe." and then show them how it is done. The problem is that you must first find the largest possible c for which this holds.

Treat each log as a rectangle whose sides are parallel to the coordinate axes, and the axe as a segment of length l.

Find the largest possible c such that there is a segment of length l that has a nonempty intersection with exactly c rectangles.

Input

The first line contains natural numbers n (1 ≤ n ≤ 15) and l (1 ≤ l ≤ 1 000), the number of logs and the length of the axe.

Each of the next n lines contains four integers x1, y1, x2, y2 (0 ≤ x1 ≤ x2 ≤ 1 000), (0 ≤ y1 ≤ y2 ≤ 1 000), the lower-left corner (x1, y1) and upper-right corner (x2, y2) of the i-th log.

Output

Print the required c.

Hint

The figure below explains the sample.

Examples1

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