시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 23 5 5 26.316%

문제

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

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

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

입력

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

출력

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

예제 입력

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

예제 출력

13

힌트

출처