보리스

필립의 고향에서는 세계에서 가장 아름다운 광고판을 자주 볼 수 있다. 이 광고판에는 다름 아닌 수학 교사 보리스와 함께 ``보리스를 믿으세요''라는 문구가 적혀 있다. 당연히 필립은 이 아름다운 광고판을 모으는 데 완전히 빠졌고, 이제 가능한 한 많은 보리스를 수집할 수 있도록 도시의 기차역 사이를 이동하는 경로를 최적화하는 데 여러분의 도움이 필요하다.

필립은 광범위한 인맥을 통해 가까운 미래에 $N$대의 기차가 도시에서 출발한다는 사실을 알아냈다. 각 기차에 대해, 그는 추적을 시작한 뒤 몇 초 후에 출발하는지, 기차에 몇 명의 보리스가 타고 있는지, 그리고 미터 단위로 주어지는 기차역의 좌표를 알고 있다. 기차에 있는 보리스들을 수집하려면 기차가 출발하는 바로 그 시각에 역에 있어야 하지만, 원한다면 일찍 도착해 차분히 기차를 기다려도 된다. 필립은 보리스를 매우 사랑하고 자신의 고향에서 멀어지는 기차에 갇히고 싶지 않기 때문에, 기차에 있는 모든 보리스를 매우 빠르게 집어 들며 이를 0초 만에 해낸다. 아무리 일찍 도착하더라도 기차가 출발하기 전에는 보리스들을 수집할 수 없다는 점에 유의하라. 기차 문은 출발 시각이 되어서야 열리기 때문이다.

보리스들을 쫓는 것처럼 긴박한 상황에서는 필립이 방향을 정확히 파악하는 일이 매우 힘들어진다. 길을 잃지 않기 위해 그는 오직 정북쪽, 정남쪽, 정동쪽 또는 정서쪽으로만 이동하는 것을 선호하며, 그러면 자신이 어디로 향하고 있는지 더 쉽게 알 수 있다.

필립에게는 모험을 준비할 시간이 충분하므로, 그는 도시의 어느 곳에서든 출발할 수 있다. 출발한 뒤에는 1미터/초의 속도로 이동한다. 필립에게는 매우 큰 배낭이 있으므로, 한 번에 원하는 만큼 많은 보리스를 운반할 수 있다.

필립이 수집할 수 있는 보리스의 최대 수는 얼마인가?

채점

여러분의 풀이는 각각 일정한 점수가 배정된 테스트 그룹들의 집합으로 채점된다. 각 테스트 그룹에는 테스트 케이스들의 집합이 포함된다. 한 테스트 그룹의 점수를 얻으려면 그 테스트 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제한 조건

$1$ |$8$| $N \le 2$

$2$ |$31$| $N \le 16$

$3$ |$33$| $t, x, y \le 50$ 그리고 $s = 1$.

$4$ |$28$| 추가 제한 조건 없음.

첫 번째 줄에는 기차의 수를 나타내는 정수 $N$ ($1 \le N \le 2,000$)이 주어진다.

이어서 각각 하나의 기차를 설명하는 $N$개의 줄이 주어진다. 각 줄에는 네 정수, 즉 추적을 시작한 뒤 기차가 출발할 때까지의 초 단위 시간 $t$ ($0 \le t \le 5 \cdot 10^8$), 기차에 있는 보리스의 수 $s$ ($1 \le s \le 500,000$), 그리고 기차가 출발하는 역의 좌표 $x, y$ ($0 \le x, y \le 5 \cdot 10^8$)가 주어진다.

정확히 같은 역에서 같은 시각에 출발하는 두 기차는 없다.

필립이 수집할 수 있는 보리스의 최대 수를 나타내는 정수 하나를 한 줄에 출력한다.

세 번째 예제 케이스에는 네 번의 출발이 있다. 입력에 나타나는 순서대로 이들을 기차 $0$부터 기차 $3$까지라고 부르겠다.

필립이 지점 $(493,377)$에서 출발하면, 시각 $148$에 기차 $3$에서 보리스 $952$명을 수집할 수 있다. 그런 다음 기차 $1$에 도달하려면 정확히 $164$미터를 걸어야 하며, 여기에는 $164$초가 걸린다. 이 기차는 $312$에 출발하며, 이는 기차 $3$이 출발한 뒤 $164$초 후이다. 따라서 그는 기차 $1$에 정확히 제시간에 도착하여 그 기차의 보리스 $911$명을 수집할 수 있다. 그곳에서 기차 $2$까지 걸어가 보리스 $927$명을 수집할 수 있는 시간은 $6$초이다. 총 $952 + 911 + 927 = 2790$명의 보리스를 수집할 수 있다.