팬더 밥 주기
시간 제한2초메모리 제한128 MB
맛 지수가 엄격히 증가하고 이동 거리가 목적지의 대나무 개수 이하인 대나무 숲 방문 순서 중 가장 긴 것을 찾는 문제입니다.
문제
테디라는 팬더는 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