산행

Ignas는 친구들과 생일 파티를 열 계획이었다. 그러나 전염병 대유행과 격리 조치로 계획이 어그러졌고, 그는 모임을 열지 않기로 했다.

다행히 생일 직전 국내 역학 상황이 크게 나아졌다. 국경을 다시 열면서 가장 먼저 Bitkalnija행 항공편 운항이 재개되었다. Bitkalnija에는 감염자가 한 명도 없었기 때문이다. Ignas는 생일을 기념해 그곳에 가서 Bitkalnija의 가장 높은 봉우리에 오르기로 했다. 등산을 위해 그는 가이드를 고용했다.

Ignas가 긴 공백 뒤 처음 맞은 가이드 고객이었으므로, 가이드는 가장 높은 봉우리에 오르기 전에 원하는 다른 봉우리에도 무료로 함께 가 주겠다고 제안했다. 봉우리 $V$는 다음 두 조건을 모두 만족하면 방문할 수 있다.

• $V$의 높이는 이미 방문한 봉우리들의 높이보다 낮지 않아야 한다.
• $V$는 Bitkalnija의 가장 높은 봉우리로부터 이미 방문한 봉우리들보다 멀지 않아야 한다.

Ignas는 이 소식에 크게 기뻐했다. 지도를 살펴본 그는 각 봉우리가 자신에게 얼마나 흥미로운지 정하고, 그 정도를 정수로 매겼다.

가이드와 함께 Ignas가 오를 수 있는 봉우리들의 흥미도(매력) 합의 최댓값은 얼마인가?

첫 줄에 산의 개수 $N$이 주어진다.

이어지는 $N$개의 줄에는 공백으로 구분된 정수 네 개 $x_i$, $y_i$, $h_i$, $d_i$가 주어진다. 이는 좌표 $(x_i, y_i)$에 높이 $h_i$인 봉우리가 있고, Ignas가 그 봉우리의 흥미도를 $d_i$로 매겼다는 뜻이다.

Ignas가 가이드와 함께 오를 수 있는 봉우리들의 흥미도 합의 최댓값을 정수 하나로 출력한다.

• $2 \le N \le 100000$
• $-1000 \le x_i, y_i \le 1000$
• $1 \le h_i, d_i \le 100000$
• 모든 산은 서로 다른 위치에 있고, 가장 높은 산은 정확히 하나다.