Informatica Online Judge

  정과프 해적단 [2166 / 0876]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 0   Total Tried : 0


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net(33rd 김동현)]

Background

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

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

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

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

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

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

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

Input

첫 번째 줄에는 서해에 있는 섬의 개수 N (1≤N≤2000) 과 동건이가 최소로 모아 가야 하는 보물의 가치 M (1≤M≤1012) 이 주어진다.

다음 N개의 줄에는 각 섬의 x좌표, y좌표, 보물 가치, 금고 강도를 나타내는 4개의 정수 xi, yi, vi, hi 가 공백을 사이에 두고 주어진다. (모두 1 이상 109 이하)

Output

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

IO Example

입력
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

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]