Boris

Philip의 고향에 있는 기차에서는 세계에서 가장 멋진 광고판을 볼 수 있다. 이 광고판에는 수학 선생님 Boris의 사진과 "Boris와 함께 계산하자"라는 문구가 함께 있다. Philip은 이 멋진 광고판을 모으는 데 완전히 사로잡혔고, 이제 도시의 기차역 사이를 오가는 경로를 최적화하여 최대한 많은 Boris를 얻는 데 당신의 도움이 필요하다.

Philip은 넓은 인맥을 통해 가까운 미래에 $N$개의 기차가 도시에서 출발할 것이라는 사실을 알게 되었다. 각 기차에 대해 그는 출발 시각(사냥을 시작한 후 초 단위), 기차에 있을 Boris의 수, 그리고 기차역의 좌표(미터 단위)를 알고 있다. 기차에 있는 Boris를 얻으려면 그는 기차가 출발하는 바로 그 초에 늦어도 도착해야 하지만, 원한다면 미리 도착해서 여유롭게 기차를 기다릴 수도 있다. Philip은 Boris를 너무나 사랑하고, 자신을 고향에서 멀어지게 할 기차에 갇히고 싶지 않기 때문에, 기차에 있는 모든 Boris를 0초 만에 매우 빠르게 집어 올린다. 그가 아무리 일찍 도착하더라도 기차의 출발 시각 전에는 Boris를 가져갈 수 없다는 점에 유의하라. 그때가 되어서야 기차로 들어가는 문이 열리기 때문이다.

Boris를 쫓는 것과 같은 스트레스가 많은 상황에서 Philip은 방위를 정확히 파악하는 것이 매우 힘들다. 길을 잃지 않기 위해 그는 북쪽, 남쪽, 동쪽, 서쪽으로만 똑바로 이동하고 싶어 하며, 그래야 자신이 어디로 가고 있는지 더 쉽게 알 수 있다.

Philip은 모험을 준비할 시간이 충분하기 때문에 도시 어디에서든 시작할 수 있다. 그런 다음 움직이기 시작하면 속도 1미터/초로 이동한다. Philip은 매우 큰 배낭을 가지고 있어서 한 번에 얼마든지 많은 Boris를 운반할 수 있다.

Philip이 모을 수 있는 최대 Boris 수는 얼마인가?

첫 번째 줄에는 정수 $N$ ($1 \le N \le 2\,000$)이 주어지며, 이는 기차의 수이다.

그다음 각 기차당 한 줄씩 주어진다. 각 줄에는 네 개의 정수가 있다: 출발 시각 $t$ (시작 후 초 단위, $0 \le t \le 5 \cdot 10^8$), 기차에 있는 Boris의 수 $s$ ($1 \le s \le 500\,000$), 그리고 기차가 출발하는 역의 좌표 $x, y$ ($0 \le x, y \le 5 \cdot 10^8$).

두 기차가 정확히 같은 역에서 동시에 출발하지 않는다.

Philip이 모을 수 있는 최대 Boris 수를 나타내는 정수 한 줄을 출력한다.

세 번째 예제에는 네 번의 출발이 있다. 이를 입력 순서대로 기차 $0$부터 기차 $3$이라고 부르자.

Philip이 점 $(493,377)$에서 시작하면 시각 $148$에 기차 $3$에서 $952$개의 Boris를 얻을 수 있다. 그런 다음 정확히 $164$미터를 걸어야 하며(이는 $164$초가 걸린다) 기차 $1$로 간다. 기차 $1$의 출발 시각은 $312$이며, 이는 기차 $3$ 이후 $164$초이다. 따라서 그는 정확히 기차 $1$에 도착하여 $911$개의 Boris를 얻을 수 있다. 거기서부터 그는 $6$초의 여유를 두고 기차 $2$로 걸어가 $927$개의 Boris를 얻을 수 있다. 총 $952+911+927=2790$개의 Boris를 얻는다.