1675번 - 팬더 밥주기

테디라는 팬더는 N개의 대나무 숲을 가진 숲속에 산다. 각각의 대나무 숲은 평면상의 점으로 표현된다. i번째 대나무 숲은 L_i개의 대나무와 W_i라는 '맛있는 정도'를 가진다.

테디는 매일 선택된 한 개의 대나무 숲의 모든 대나무들을 먹어치운다. 단 현재 대나무 숲이 그 전날 선택한 대나무 숲보다 '맛있는 정도'가 더 좋아야만 한다.

테디가 걷는 시간이 길면 길수록 그는 더 많은 대나무를 기대하게 되므로, 만약 그가 이전 대나무 숲으로부터 걸어온 거리가 현재 도달한 대나무 숲의 대나무 수보다 적다면 울음을 터뜨린다.

두 점(x₀, y₀)과 (x₁, y₁)사이의 거리는 |x₀-x₁| + |y₀-y₁|로 표현된다. 따라서 테디는 동서남북 방향으로만 움직인다.

문제는 테디를 하나의 대나무 숲에 데려다 놓으면, 그는 최대 며칠 동안 울음을 터뜨리지 않는지를 구하는 것이다. 테디가 처음 있는 대나무 숲은 당신이 정하는 것이다.

첫째 줄에 대나무 숲의 개수 N이 주어진다. 두 번째 줄부터 N+1번째 줄까지 i+1번째 줄에는 i번째 대나무 숲의 위치를 나타내는 X_i, Y_i와 맛있는 정도를 나타내는 W_i, 대나무의 개수 L_i가 공백으로 구분되어 주어진다.

첫째 줄에 울음을 터뜨리지 않는 최대 일 수를 출력하시오.

• 1 ≤ N ≤ 100,000
• 0 ≤ X_i, Y_i ≤ 100,000
• 0 ≤ W_i ≤ 50,000
• 0 ≤ L_i ≤ 200,000