관광지로 유명한 아르미 도시에서는 아래 <그림 1>에서 보는 것처럼 일직선으로 된 길을 따라 자그만 조각품을 장대 끝에 달아 두었다. 장대의 높이와 장대의 간격은 설치자의 예술 감각에 따라 다양하다.

<그림 1> 5개의 조각품이 설치된 모습

장대 끝에 달린 조각품이 야간에도 모두 다 잘 보일 수 있도록 하기 위해 조명등을 설치하려고 한다. 조명등 역시 장대 끝에 설치하는데, 조명등 위에 있는 갓 때문에 아래 방향 좌우 45° 범위 내에 있는 공간만 밝게 비춘다. 조명등은 필요한 곳에 새로운 장대를 세워 그 끝에 설치하는데, 이미 조각품이 설치된 곳에도 조명등을 설치할 수 있다. 아래 <그림 2>는 <그림 1>에서 보인 5개의 조각품을 비추기 위해 3개의 조명등을 설치한 예를 보여준다. 처음 두 조명등은 새로운 위치에 막대를 세워 그 끝에 조명등을 설치하였고, 세 번째 조명등은 설치된 조각 위치와 동일한 곳에 설치되었다.

<그림 2> 조명등이 설치된 예

<그림 3>은 조명등을 1개만 설치하여 전체 조각품을 비추는 예를 보여준다.

조명등을 높이 달수록 더 많은 면적을 밝게 할 수 있지만, 그에 비례하여 더 비싼 등을 달아야 한다. 즉, 각 조명등의 설치 비용은 그 조명등이 밝히는 삼각형 모양의 면적이다.

설치된 모든 조각품을 비추기 위해 최소 비용으로 조명등을 설치하려고 한다.

제한사항

$1 \leq T \leq 100$
$1 \leq N \leq 100,000$
$1 \leq x_i, h_i \leq 100,000,000$
모든 테스트 케이스에서 $N$의 합은 1,000,000 이하이다.
$T, N, x_i, h_i$는 모두 정수이다.

조명등

📃 해결할 문제

💻 입력

🖨️ 출력

💻 예제 입력 1

🖨️ 예제 출력 1