판다 스키
시간 제한1초메모리 제한512 MB
각 게이트의 점수와 이동 한계가 주어질 때, 꼭대기에서 바닥까지 내려가며 게이트를 지날 때 얻는 최대 점수를 구한다. 같은 게이트의 점수는 한 번만 센다.
문제
동계 올림픽이 다가오고 판다 씨는 스키 종목에 나가기 위해 열심히 훈련해 왔다. 이 종목은 높이 H인 산 라르에서 열린다. 누구나 정상에서 산기슭까지 중심 경로를 따라 내려올 수 있다. 난이도를 높이기 위해 점수가 매겨진 N개의 게이트가 여러 높이에, 중심 경로의 왼쪽이나 오른쪽에 놓여 있다. 목표는 정상에서 산기슭까지 내려오면서 게이트의 일부를 지나 점수를 얻는 것이다.
i번째 게이트는 높이 Yi에, 중심 경로에서 오른쪽으로 Xi만큼 떨어진 곳에 있다. Xi가 음수면 중심 경로의 왼쪽에 있다. i번째 게이트를 지나면 Si점을 얻으며, 같은 게이트를 여러 번 지날 수 있지만 점수는 처음 지날 때만 얻는다. 같은 점에 놓인 게이트는 없다.
판다 씨는 점수를 최대한 많이 얻고 싶어 한다. 게다가 판다 씨는 자신이 스키를 잘 타지 못한다는 것을 알고 있고, 일부 게이트는 방문하지 못할 것이다. 창피를 당하지 않기 위해 판다 씨는 경사의 각도, 눈의 양 등을 바탕으로 각 게이트에 쉬움 점수 Ei를 매긴다(점수가 높을수록 쉽다).
구체적으로, 판다 씨는 max(|Xj− Xi|, Yi − Yj) ≤ Ei이고 Yi ≥ Yj일 때 i번째 게이트에서 j번째 게이트로 이동할 수 있다고 계산했다. 또한 정상에서 어떤 게이트로도 갈 수 있고, 어떤 게이트에서도 산기슭으로 갈 수 있다.
판다 씨는 산을 내려가는 가능한 경로의 수에 압도되어, 최대 점수를 얻을 경로를 찾는 데 여러분의 도움이 필요하다.
입력
프로그램은 표준 입력에서 읽는다. 입력의 첫 줄에는 두 양의 정수 N과 H가 주어진다. 다음 N개의 줄에는 각각 4개의 정수 Xi, Yi, Si, Ei가 주어진다. (i + 1)번째 줄이 Xi, Yi, Si, Ei를 나타낸다.
출력
프로그램은 표준 출력에 판다 씨가 얻을 수 있는 최대 점수인 정수 하나를 한 줄로 출력한다.