시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB101171625.000%

문제

기훈이는 각각 계단에 몇 개의 사탕이 놓여있는 계단을 찾았다. 기훈이는 가능하면 많은 사탕을 모으려고 한다. 각각의 계단은 이차원 평면에서 x축에 평행하고 양의 y좌표 값을 갖는 직선으로 표현될 수 있다. 계단은 모두 겹치지 않으며, 같은 끝점을 갖는 계단은 없다.

기훈이가 계단위에 있을 때, 기훈이는 계단의 양 끝으로 자유롭게 움직일 수 있고, 계단 위의 사탕을 모두 모을 수 있다. 기훈이는 계단 위의 한 점에서 (끝 점도 포함) 다른 계단 위의 한 점으로 점프 할 수 있다. 단, 그 때 두 점 사이의 거리가 K보다 작거나 같아야 한다. 그리고, 기훈이는 y좌표가 현재와 같거나 큰 곳으로만 이동할 수 있다.

기훈이는 좌표 (0, 0)에서 시작한다. 그리고 첫 번째 점프를 위해서 자유롭게 이동할 수 있다. 기훈이가 모을 수 있는 사탕 개수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 주어지는 계단의 개수 N과 K가 주어진다. 둘째 줄부터 N개의 줄에 각 계단의 정보가 주어진다. 계단의 정보는 계단 위의 사탕 개수, 가장 왼쪽 점의 X좌표, Y좌표, 계단의 길이와 같이 주어진다. N은 50보다 작거나 같은 자연수이고, X와 Y좌표는 10,000보다 작거나 같은 자연수이다. 계단의 길이는 최대 1,000인 자연수이고, 사탕의 개수는 9,999보다 작거나 같은 음이 아닌 정수이다. K는 10,000보다 작거나 같은 자연수이다.

계단의 양 끝 점이 겹치거나, 끝 점을 공유하는 경우는 없다.

출력

첫째 줄에 기훈이가 모을 수 있는 사탕 개수의 최댓값을 출력한다.

예제 입력 1

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

예제 출력 1

13

예제 입력 2

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

예제 출력 2

47

예제 입력 3

4 10
1 1 2 4
3 6 4 1
5 2 1 7
7 8 2 4

예제 출력 3

16

예제 입력 4

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

예제 출력 4

0

예제 입력 5

3 5
2 1 6 3
0 8 6 6
5 9 1 3

예제 출력 5

7

출처