개구리
시간 제한3초메모리 제한512 MB
1번부터 n번까지 놓인 개구리마다 이동 범위 r_i와 실력 s_i가 주어질 때, 세 개구리가 함께 이동할 수 있는 돌이 존재하도록 세 마리를 골라 실력 합의 최댓값을 구한다.
문제
개구리는 뛰어오르고 개굴개굴 울기만 잘한다고 생각할지 모르지만, 사실 코딩도 꽤 능숙하다! 여러분의 임무는 OpenFrogCup에 나갈 최고의 팀을 이룰 개구리 세 마리를 고르는 것이다.
개구리들이 좋아하는 연못에는 n개의 돌이 일렬로 놓여 있고, 서로 1미터씩 떨어져 있다. 모든 돌 위에는 개구리 한 마리가 앉아 있다. 돌(과 개구리)에는 왼쪽에서 오른쪽으로 1, 2, . . . , n의 번호가 붙어 있다. i번 개구리는 i번 돌에 앉아 있고, 두 매개변수로 설명된다: 뛸 수 있는 거리 ri와 프로그래밍 실력 si. 개구리는 ri미터보다 멀지 않은 돌, 즉 인덱스 j가 [i − ri, i + ri]에 있는 돌이라면 어디든 갈 수 있다. 각 개구리는 최대 한 번만 뛰려고 한다.
OpenFrogCup에 나갈 팀은 함께 훈련할 수 있는 정확히 세 마리로 구성된다. 즉, 세 개구리가 모두 뛰어갈 수 있는 돌이 하나 있어야 한다(길이가 0인 점프도 허용된다). 그러한 팀의 프로그래밍 실력 합의 최댓값을 구하라.
문제의 제한은 가능한 세 마리 팀이 항상 적어도 하나 존재함을 보장한다.
입력
입력의 첫 줄에는 테스트 케이스의 수 z가 주어진다 (1 ≤ z ≤ 30). 테스트 케이스가 이어지며, 각각은 다음 형식이다:
테스트 케이스의 첫 줄에는 정수 n이 주어진다 (3 ≤ n ≤ 200 000). 이는 돌(이자 개구리)의 수이다. 이어지는 n개의 줄에는 각각 두 정수 ri, si가 주어진다 (1 ≤ ri, si ≤ 200 000). 이는 i번 개구리의 거리와 실력이다.
모든 테스트 케이스에 걸친 n 값의 합은 500 000을 넘지 않는다.
출력
각 테스트 케이스마다 세 마리 개구리 팀의 실력 합의 최댓값을 정수 하나로 출력한다.