시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 61 18 14 45.161%

문제

정과프 해적단이 나타났다! 정보과학프로젝트 수강생들로 이루어진 정과프 해적단은 가차없기로 악명이 높다. 그 두목의 정체를 아는 사람은 극히 일부밖에 없으며, '킹-갓'이라는 별명만이 떠돌아다닐 뿐이다. 세계 각국의 고귀한 보물들을 휩쓸고 다니던 정과프 해적단은 어느덧 우리나라의 아름다운 다도해, 서해만을 남겨두고 있었으니..

두목의 충실한 오른팔인 동건이는 서해에 있는 $N$개의 섬들에 숨겨져 있는 보물들을 가지고 오라는 명을 받았다. 동건이의 출발 위치는 ($0$, $0$)이며, 해적단의 아지트인 SRC 123호는 ($10^9$, $10^9$)에 위치해 있다. 남서풍이 심하게 불고 있어서, 동건이는 $x$좌표나 $y$좌표가 감소하는 방향으로 움직일 수 없다.

각 섬에는 보물이 숨겨진 금고가 하나씩 있고, 이 금고는 특수 제작된 해체기로 열 수 있다. 금고는 담긴 보물의 가치 $v_i$와 강도 $h_i$를 가지는데, 금고가 너무 단단하면 해체기가 망가지고, 너무 약하면 보물이 같이 부서지기 때문에 해체기를 미리 적절히 설정해야 한다. 해체기는 ($0$, $0$)에서 출발할 때 딱 한 번 설정할 수 있는데, 강도가 [$x$, $y$] 범위에 있는 금고를 열 수 있도록 설정하려면 ($y-x$)원의 비용이 든다.

동건이는 해체기 설정 비용 정도는 해적단에서 지원해 주리라 생각했지만, 두목은 자신의 부하에게도 가차없었다. 우리의 불쌍한 동건이가 두목과 연락하는 모습을 지켜보자.

"저... 두목님... 그 해체기 설정 비용은 지원해 주시는 거..."

"안 줘. 니 돈 써. 아 맞다, 보물 $M$원어치 안 모아오면 너 짜를거야. (뚝! 뚜... 뚜... 뚜... 뚜... 뚜...)"

동건이는 눈 앞에서 계약서를 불태워버리는 무자비한 두목의 모습을 상상하면서 두려움에 떨고 있다. 동건이가 해적단에서 쫓겨나지 않기 위해서는 사비를 최소 얼마나 써야 할까?

입력

첫 번째 줄에는 서해에 있는 섬의 개수 $N$ ($ 1 \le N \le 2\, 000$) 과 동건이가 최소로 모아 가야 하는 보물의 가치 $M$ ($1 \le M \le 10^{12}$) 이 주어진다.

다음 $N$개의 줄에는 각 섬의 $x$좌표, $y$좌표, 보물 가치, 금고 강도를 나타내는 4개의 정수 $x_i$, $y_i$, $v_i$, $h_i$ 가 공백을 사이에 두고 주어진다. (모두 $1$ 이상 $10^{9}$ 이하)

출력

동건이가 해적단에서 쫓겨나지 않기 위해 써야 하는 최소의 사비를 출력한다. 만약 동건이가 어떻게 해도 해적단에서 쫓겨나야 한다면 "-1"을 출력한다. (따옴표 제외)

예제 입력

3 5
1 1 2 5
2 2 3 3
3 3 4 9

예제 출력

2

예제 입력 2

2 5
1 2 4 1
2 1 4 2

예제 출력 2

-1

힌트