정과프 해적단

정과프 해적단이 나타났다. 정보과학프로젝트 수강생으로 이루어진 이 해적단은 가차없기로 악명이 높다. 두목의 정체를 아는 사람은 극히 드물고 '킹갓'이라는 별명만 떠돈다. 세계 각국의 보물을 휩쓸고 다닌 해적단에게 이제 남은 곳은 우리나라의 서해뿐이다.

두목의 오른팔 동건이는 서해에 있는 $N$개의 섬에 숨겨진 보물을 가져오라는 명을 받았다. 출발 위치는 ($0$, $0$)이고 해적단의 아지트는 ($10^9$, $10^9$)에 있다. 남서풍이 거세게 불어서 동건이는 $x$좌표나 $y$좌표가 줄어드는 방향으로 움직이지 못한다. 따라서 어떤 섬에 들른 다음에 들를 수 있는 섬은 $x$좌표와 $y$좌표가 모두 그 섬 이상인 섬뿐이다.

섬마다 보물이 든 금고가 하나씩 놓여 있다. $i$번 섬의 금고에는 보물의 가치 $v_i$와 강도 $h_i$가 정해져 있다. 금고는 특수 제작한 해체기로 연다. 강도가 너무 높으면 해체기가 망가지고 너무 낮으면 보물까지 부서지므로 해체기를 미리 맞춰 두어야 한다. 해체기 설정은 ($0$, $0$)에서 출발할 때 딱 한 번만 할 수 있고, 강도가 $a$ 이상 $b$ 이하인 금고를 열도록 맞추는 데 $b - a$원이 든다. 들른 섬이라도 금고를 열지 않고 지나갈 수 있다.

동건이는 설정 비용쯤은 해적단이 대 주리라 생각했지만, 두목은 제 부하에게도 똑같이 가차없었다.

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

'안 줘. 니 돈 써. 아 맞다, 보물 $M$원어치 안 모아 오면 너 짜를 거야.'

동건이가 해적단에서 쫓겨나지 않으려면 사비를 최소 얼마나 써야 하는지 구하여라.

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

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

동건이가 써야 하는 최소 사비를 한 줄에 출력한다. 어떻게 해도 보물을 $M$원어치 이상 모을 수 없으면 -1을 출력한다.