조명등

관광지의 일직선 길을 따라 $N$개의 조각품이 설치되어 있다. $i$번째 조각품의 위치는 $x_{i}$, 높이는 $h_{i}$이다.

밤에 모든 조각품을 비추기 위해 조명등을 설치한다. 조명등은 길 위의 원하는 위치에 설치할 수 있으며, 조명등의 높이는 원하는 만큼 정할 수 있다.

높이가 $H$인 조명등은 아래 방향 좌우 $45^{\circ}$ 범위만 비춘다. 따라서 조명등의 위치를 $p$라 하면, 조각품 $(x_{i}, h_{i})$가 비춰지려면 $|x_{i} - p| \le H-h_{i}$여야 한다.

여러 조명등을 설치할 수 있으며, 조각품 하나가 여러 조명등에 의해 비춰져도 된다.

또한 하나의 조명등만으로 모든 조각품을 비추는 것도 가능하다.

조명등 하나의 설치 비용은 그 조명등이 비추는 삼각형의 면적이다. 조명등을 높게 설치할수록 더 넓은 범위를 비출 수 있지만 비용도 증가한다.

모든 조각품을 비추기 위한 최소 설치 비용을 구하여라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스마다 첫째 줄에 조각품의 수 $N$이 주어지고, 다음 $N$개의 줄에 $i$번째 조각품의 위치와 높이 $x_{i}$, $h_{i}$가 주어진다.

• $1 \le T \le 100$
• $1 \le N \le 100,000$
• $1 \le x_i, h_i \le 100,000,000$
• $x_i$는 증가하는 순서로 주어진다.
• 모든 테스트 케이스에서 $N$의 합은 $1,000,000$ 이하이다.

각 테스트 케이스마다 최소 비용을 소수점 아래 두 자리까지 정확히 출력한다.

• 5점 상당의 테스트 케이스에서 $N \le 3$을 만족한다.
• 30점 상당의 테스트 케이스에서 $N \le 1,000$을 만족한다.
• 20점 상당의 테스트 케이스에서 모든 $h_{i}$가 같음을 만족한다.