마법 던전의 마물 퇴치

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는 마물이 빼앗아 가는 마력의 총합을 최소화하고자 한다.

입력의 첫 줄에 테스트 케이스의 수 $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 < j \le N$인 모든 $i, j$에 대하여: $p_i \neq p_j$