#288 보물찾기

문제

지문 언어

길이가 $L$ 인 선분 $[0,L]$ 위에서 $N$ 명의 사람이 보물을 찾고 있다. 사람들은 좌표가 작은 순서대로 $1,2,\cdots,N$ 번이며, $i$ 번 사람의 위치는 $A_i$ 이다.

각 사람은 왼쪽 또는 오른쪽 중 한 방향을 선택하여 탐색한다. $i$ 번 사람은 자신의 위치에서 선택한 방향으로 최대 $B_i$ 만큼 떨어진 곳까지 탐색할 수 있다. 단, 선분의 바깥으로 나갈 수 없고 다른 사람의 위치를 넘어서 탐색할 수 없다.

편의를 위해 $A_0=0$ , $A_{N+1}=L$ 이라 하자. 번 사람이 왼쪽을 선택하면 탐색하는 구간은

[\max(A_{i-1},A_i-B_i),A_i]

이고, 오른쪽을 선택하면 탐색하는 구간은

[A_i,\min(A_{i+1},A_i+B_i)]

이다.

$N$ 명이 탐색할 수 있는 구간은 각 사람이 탐색하는 구간들의 합집합이다. 모든 사람이 탐색할 방향을 적절히 정했을 때, 이 합집합의 길이의 최댓값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

각 테스트 케이스마다 탐색할 수 있는 구간의 길이의 최댓값을 한 줄에 출력한다.

#	점수	제한
1	34	$N \leq 18$ . 모든 테스트 케이스에 대한 $N$ 의 합은 $18$ 이하이다.
2	23	$N \leq 5\,000$ .

입력

출력

6
7

첫 번째 테스트 케이스에서는 한 사람이 오른쪽을 보면 좌표 $4$ 부터 $10$ 까지 길이 $6$ 의 구간을 탐색할 수 있다.

두 번째 테스트 케이스에서는 두 사람이 같은 방향을 보는 방법 중 하나를 선택하면 길이 $7$ 의 구간을 탐색할 수 있다.