Under construction

Still being built. Things may change

Candy Stair Climb

Time limit2sMemory limit128 MB

Summary
Find the maximum candies collectible by jumping between horizontal stair segments within distance K, never decreasing height, starting from the ground.
Level

Medium7 of 10

Topics
Topological sort, Graph, Dynamic programming, Geometry
Solved
No attempts yet

Problem

Kihoon found several stairs with candies on them. Each stair has a fixed number of candies, and he wants to collect as many candies as possible.

Each stair is represented on the two-dimensional plane as a line segment parallel to the x-axis. Every stair has a positive y-coordinate. No two stairs overlap, and no two stairs share an endpoint.

When Kihoon is on a stair, he may move freely between the two endpoints of that stair and collects all candies on it. He may also jump from any point on one stair, including an endpoint, to any point on another stair, including an endpoint. The distance between the two chosen points must be at most K, and the destination y-coordinate must not be smaller than his current y-coordinate.

Kihoon starts at (0, 0). Before making the first jump, he may move freely along the x-axis. Find the maximum number of candies he can collect.

Input

The first line contains the number of stairs N and the jump distance limit K.

Each of the next N lines contains four integers C, X, Y, and L: the number of candies on the stair, the x-coordinate of its left endpoint, its y-coordinate, and its length. The stair is the segment from (X, Y) to (X + L, Y).

  • 1 <= N <= 50
  • 1 <= K <= 10,000
  • 1 <= X, Y <= 10,000
  • 1 <= L <= 1,000
  • 0 <= C <= 9,999

No two stairs overlap or share an endpoint.

Output

Print the maximum number of candies Kihoon can collect.

Examples5

  1. Example 1

    Input
    6 2
1 1 1 2
2 1 3 1
3 1 4 1
4 4 1 2
3 5 2 1
5 5 3 1
    Expected output
    13

  2. Example 2

    Input
    10 4
2 2 1 2
8 9 1 2
7 4 3 1
4 6 3 2
1 10 3 2
4 5 5 2
7 2 6 4
5 8 6 3
11 1 8 2
4 10 9 2
    Expected output
    47

  3. Example 3

    Input
    4 10
1 1 2 4
3 6 4 1
5 2 1 7
7 8 2 4
    Expected output
    16

  4. Example 4

    Input
    5 10
0 1 1 11
10 26 83 1
11 29 88 23
2 22 22 15
0 3 5 8
    Expected output
    0

  5. Example 5

    Input
    3 5
2 1 6 3
0 8 6 6
5 9 1 3
    Expected output
    7