Treasure Hunting

시간 제한1초메모리 제한1024 MB

요약

원점에서 출발해 1번부터 N번까지 순서대로 보물을 방문하거나 건너뛰며, 맨해튼 이동 시간과 2z의 발굴 시간을 합쳐 제한 시간 T 안에 원점으로 돌아올 때 얻을 수 있는 최대 가치를 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 그리디
정답자: 아직 제출이 없습니다

문제

Farmer John (also known as FJ) has discovered a map containing the locations of buried hidden treasures on his farm. The treasures are numbered sequentially 1..N (1 ≤ N ≤ 100). Each treasure is hidden at a different (x,y) pair of integer coordinates buried at some integer depth (a positive integer denoted as z), and has some integer value (V).

FJ moves between two points in a "Manhattan" style, rather than on a diagonal line. For example, to move from (1,2) to (5,7), he would move 4 units for the first coordinate and then 5 units for the second coordinate. FJ moves at a rate of one unit per minute and digs at a rate of 0.5 units per minute. You are also given an integer time limit (T) on the total time FJ can spend hunting treasure.

Starting at the origin (0,0), FJ considers the treasures in sequence from 1 to N, and for each, he can decide to skip over the treasure or to move to it and dig it up (which takes some amount of time, but gives him some amount of value in return when the treasure is completely unearthed). Your task is to determine the maximum amount of value FJ can obtain within his time limit. FJ must return to the origin before his time limit expires.

입력

Line 1: Two integers: N (1 ≤ N ≤ 80) and T (1 ≤ T ≤ 1,000,000)
Lines 2..N+1: Four integers representing a treasure: x (-100 ≤ x ≤ 100), y (-80 ≤ y ≤ 80), z (0 < z ≤ 25), and V (1 ≤ V ≤ 1000)

출력

A single line with a single integer that is maximum amount of value FJ can dig up during his treasure hunt.

예제1

예제 1
입력
```
3 20
2 3 2 5
-5 0 8 51
2 -2 1 14
```
예상 출력
```
19
```