마법 던전의 마물 퇴치

Bert는 마법 던전의 파수꾼인데, 던전은 지상 1층부터 1억층 (양의 정수 1 이상 $10^8$ 이하로 표현), 지하 1층부터 1억층까지 (음의 정수 $-1$ 이하 $-10^8$ 이상으로 표현) 구분되어있고, Bert의 숙소는 0층에 위치해있다. 최근 마법 던전에는 마력을 빼앗아가는 마물이 나타나기 시작해서 마법사 협회에서 Bert에게 마물 퇴치를 맡겼다. 구체적으로, 현재 총 $N$ 종류의 마물이 서식하고 있고 (편의상 $1$ 부터 $N$ 까지 번호가 붙어 있다), $i$ 번째 마물은 $p\_i$ 층에 서식하며, 매 시간 $w\_i$ 만큼의 마력을 던전으로부터 빼앗아간다. 서로 다른 종류의 마물은 같은 층에 서식하지 않는다. Bert는 0층에서 출발하여 매 시간 한 층씩 던전을 오르내릴 수 있고, 어떤 층에 도착하는 즉시 강력한 마법을 사용하여 순식간에 해당 층의 모든 마물을 없앨 수 있다. Bert는 당연히 마물이 빼앗아가는 마력의 총합을 최소화 하는 방법으로 마물을 퇴치하고 싶어한다.

예를 들어 $N = 4$, $p = \[-4, -13, 4, 8]$, $w = \[1, 14, 1, 1]$ 이라 하자. 즉, 지하 4층의 마물은 매 시간 1 만큼의 마력을 빼앗아가고 지하 13층의 마물은 매 시간 14 만큼의 마력을 빼앗아간다. Bert가 마물을 퇴치할 수 있는 여러 가지 방법 중 아래 두 가지 방법을 살펴보자. 이 때 편의상 $i$번째 마물이 퇴치된 시각을 $t\_i$라 하자 (따라서 $i$번째 마물이 빼앗아간 마력의 총합은 $w\_i \cdot t\_i$가 된다).

• 1, 2, 3, 4 번째 마물을 순서대로 퇴치하는 경우: 0층 -> 지하 4층 -> 지하 13층 -> 지상 4층 -> 지상 8층 순으로 이동하며, 이 때 $t = \[4, 13, 30, 34]$ 이므로 던전이 빼앗긴 마력의 총합은 $4 \cdot 1 + 13 \cdot 14 + 30 \cdot 1 + 34 \cdot 1 = 250$ 이 된다.
• 4, 3, 2, 1 번째 마물을 순서대로 퇴치하는 경우: 0층 -> 지상 8층 -> 지상 4층 -> 지하 13층 -> 지하 4층 순으로 이동하며, 이 때 $t = \[38, 29, 12, 8]$ 이므로 던전이 빼앗긴 마력의 총합은 $38 \cdot 1 + 29 \cdot 14 + 12 \cdot 1 + 8 \cdot 1 = 464$ 가 된다

이 예제의 경우, 첫 번째 방법처럼 250의 마력을 뺏기는 것이 최선이다.

다른 예로, $N = 4$, $p = \[-4, -13, 4, 8]$, $w = \[1, 1, 1, 1]$ 이라 하자.

• 1, 2, 3, 4 번째 마물을 순서대로 퇴치하는 경우: 0층 -> 지하 4층 -> 지하 13층 -> 지상 4층 -> 지상 8층 순으로 이동하며, 이 때 $t = \[4, 13, 30, 34]$ 이므로 던전이 빼앗긴 마력의 총합은 $4 \cdot 1 + 13 \cdot 1 + 30 \cdot 1 + 34 \cdot 1 = 81$ 이 된다.
• 4, 3, 2, 1 번째 마물을 순서대로 퇴치하는 경우: 0층 -> 지상 8층 -> 지상 4층 -> 지하 13층 -> 지하 4층 순으로 이동하며, 이 때 $t = \[38, 29, 12, 8]$ 이므로 던전이 빼앗긴 마력의 총합은 $38 \cdot 1 + 29 \cdot 1 + 12 \cdot 1 + 8 \cdot 1 = 87$ 가 된다
• 3, 4, 1, 2 번째 마물을 순서대로 퇴치하는 경우: 0층 -> 지상 4층 -> 지상 8층 -> 지하 4층 -> 지하 13층 순으로 이동하며, 이 때 $t = \[20, 29, 4, 8]$ 이므로 던전이 빼앗긴 마력의 총합은 $20 \cdot 1 + 29 \cdot 1 + 4 \cdot 1 + 8 \cdot 1 = 61$ 가 된다

이 예제의 경우, 세 번째 방법처럼 61의 마력을 뺏기는 것이 최선이다.

고생하는 Bert를 위해 Alice는 "임의의 층으로 이동할 수 있는" 텔레포트 마법을 전수해주었다. 단, 이 마법은 0층의 숙소에서만 사용할 수 있으며, 0층에서 $-x$ 층 혹은 $x$ 층으로 순식간에 이동할 수 있게 해주는 대신 $x^2$ 만큼의 마력을 던전으로부터 빼앗아야 한다. 이 사정을 전해들은 마법사 협회는 마법의 남용 막기위해 "텔레포트 마법은 그 어떤 마물도 처치하기 전에 최대 한 번만 사용할 수 있다" 라는 조건 하에 마법 사용을 승인했다.

앞선 예제 중 첫 번째 예를 다시 살펴보면, "텔레포트" 마법을 사용하지 않는 경우 250의 마력을 뺏기는 것이 최선이다. 하지만 Bert가 지하 9층으로 텔레포트 한 후 (텔레포트 하는 비용은 $9^2 = 81$ 만큼의 마력이다), 2, 1, 3, 4 번째 마물을 순서대로 퇴치한다면 $t = \[13, 4, 21, 25]$ 이 되므로 던전이 빼앗긴 마력의 총합은 $81 + \left(13 + 14\cdot 4 + 21 + 25\right) = 196$ 이 된다. 이 방법이 최선이다.

앞선 예제 중 두 번째 예를 다시 살펴보면, "텔레포트" 마법을 사용하지 않는 경우 61의 마력을 뺏기는 것이 최선이다. 하지만 Bert가 2층으로 텔레포트 한 후 (텔레포트 하는 비용은 4 만큼의 마력이다), 3, 4, 1, 2 번째 마물을 순서대로 퇴치한다면 $t = \[18, 27, 2, 6]$ 이 되므로 던전이 빼앗긴 마력의 총합은 $4 + \left(18 + 27 + 2 + 6\right) = 57$ 이 된다.

이처럼 Bert 는 임의의 층으로 텔레포트를 한 후 마물을 퇴치하면 더 효율적으로 모든 마물을 퇴치할 수도 있다.

입력으로 $N$과 $p, w$ 배열이 주어졌을 때, Bert 가 마물을 모두 퇴치하는 동안 던전이 빼앗기게 되는 마력의 총합의 최솟값을 구해보자. 마법사 협회의 조건대로 텔레포트 마법은 그 어떤 마물도 퇴치하기 전에 숙소에서, 단 한 번만 사용할 수 있다 (하지만 사용하지 않아도 괜찮다).

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

각 테스트 케이스의 첫 줄에 $N$ 이 주어진다. 다음 $N$ 줄에 걸쳐 각 줄에 $p\_i, w\_i$ 가 공백으로 구분되어 주어진다.

각 테스트 케이스의 정답을 각 줄에 출력한다.

• $1 \le T \le 10$

• $1 \le N \le 1\\,000$

• $1 \le i \le N$ 인 $i$에 대하여:

  • $-100\\,000\\,000 \le p\_i \le 100\\,000\\,000$
  • $p\_i \neq 0$
  • $1 \le w\_i \le 1\\,000\\,000$

• $1 \le i \lt j \le N$ 인 $i, j$에 대하여: $p\_i \neq p\_j$