The Infosci Pirate Crew

Time limit1sMemory limit512 MB

Summary

Given N islands with coordinates, treasure values, and safe hardness, choose a monotone northeast path and a hardness interval to maximize collected value minus interval length.

Level: Hard8 of 10
Topics: Dynamic programming, Sorting, Two pointers, Segment tree
Solved: No attempts yet

Problem

The Infosci Pirate Crew has shown up. The crew is made up of students from the Information Science Project course, and it is known for showing no mercy. Hardly anyone knows who the captain is, and only the nickname 'King God' gets passed around. The crew has already swept up treasure across the world, and the West Sea is the last place left.

Donggeon, the captain's right hand, is ordered to bring back the treasure hidden on the $N$ islands of the West Sea. He starts at ( $0$ , $0$ ), and the crew's hideout sits at ( $10^9$ , $10^9$ ). A hard southwest wind is blowing, so Donggeon cannot move in any direction that decreases his $x$ coordinate or his $y$ coordinate. Once he has stopped at an island, the only islands he can stop at afterwards are the ones whose $x$ coordinate and $y$ coordinate are both at least as large.

Each island holds one safe with treasure inside. The safe on island $i$ has treasure worth $v_i$ and hardness $h_i$ . A safe opens with a custom cracking tool. A safe that is too hard wrecks the tool, and a safe that is too soft shatters the treasure with it, so the tool has to be set in advance. Donggeon can set the tool exactly once, as he leaves ( $0$ , $0$ ). Setting it to open every safe with hardness between $a$ and $b$ inclusive costs $b - a$ won. He may stop at an island and pass it by without opening its safe.

Donggeon assumed the crew would cover the setup cost, but the captain is just as harsh with his own men.

'Um, captain, the cost of setting the tool, you are covering that, right...'

'Nope. Use your own money. Oh, and if you do not bring back $M$ won worth of treasure, you are fired.'

Find the smallest amount of his own money Donggeon has to spend to keep his place in the crew.

Input

The first line contains the number of islands in the West Sea, $N$ ( $1 \le N \le 2\,000$ ), and the smallest treasure value Donggeon has to collect, $M$ ( $1 \le M \le 10^{12}$ ).

Each of the next $N$ lines contains four integers $x_i$ , $y_i$ , $v_i$ , $h_i$ separated by spaces, giving the $x$ coordinate of the island, its $y$ coordinate, the value of its treasure, and the hardness of its safe. All four values are between $1$ and $10^9$ inclusive.

Output

Print on one line the smallest amount of his own money Donggeon has to spend. If he cannot collect treasure worth $M$ or more no matter what he does, print -1.

Examples2

Example 1
Input
```
3 5
1 1 2 5
2 2 3 3
3 3 4 9
```
Expected output
```
2
```
Example 2
Input
```
2 5
1 2 4 1
2 1 4 2
```
Expected output
```
-1
```