팬더 밥 주기

테디라는 팬더는 N개의 대나무 숲이 있는 숲에 산다. 각 대나무 숲은 평면 위의 한 점으로 나타낸다. i번째 대나무 숲은 맛있는 정도 W_i와 대나무 개수 L_i를 가진다.

테디는 하루에 대나무 숲 하나를 골라 그 숲의 대나무를 모두 먹는다. 둘째 날부터는 전날 먹은 숲보다 맛있는 정도가 더 큰 숲으로만 이동할 수 있다.

테디는 오래 걸을수록 더 많은 대나무를 기대한다. 이전 숲에서 현재 숲까지 걸은 맨해튼 거리가 현재 숲의 대나무 개수 L_i보다 크면 테디는 울음을 터뜨린다. 즉, 이동하려면 |x_0 - x_1| + |y_0 - y_1| <= L_i 여야 한다.

처음 시작할 대나무 숲은 마음대로 정할 수 있다. 테디가 울지 않고 대나무를 먹을 수 있는 최대 일수를 구하라.

첫째 줄에 대나무 숲의 개수 N이 주어진다.

다음 N개의 줄 중 i번째 줄에는 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