Candy Stair Climb

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.

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.

Print the maximum number of candies Kihoon can collect.