Repelling Monsters in the Magic Dungeon

Bert is a guardian of a magic dungeon. The dungeon has floors 1 to $10^8$ above ground (written as positive integers from $1$ to $10^8$) and floors 1 to $10^8$ below ground (written as negative integers from $-1$ down to $-10^8$). Bert's lodge is on floor 0.

Recently, monsters that drain magic power from the dungeon started appearing, so the Magic Association assigned Bert to exterminate them. There are $N$ kinds of monsters in the dungeon, numbered 1 to $N$. The $i$-th kind lives on floor $p_i$ and takes $w_i$ units of magic power from the dungeon every hour. Two different kinds of monsters never live on the same floor.

Bert starts on floor 0 and can move up or down one floor per hour. As soon as he arrives on a floor, he uses a powerful spell that instantly removes all monsters on that floor. Bert wants to minimize the total magic power the monsters take.

The first line contains the number of test cases $T$.

The first line of each test case contains $N$. The next $N$ lines each contain $p_i$ and $w_i$, separated by a space.

For each test case, print the answer on its own line.

• $1 \le T \le 10$
• $1 \le N \le 1\,000$
• For all $i$ with $1 \le i \le N$:
  • $-100\,000\,000 \le p_i \le 100\,000\,000$
  • $p_i \neq 0$
  • $1 \le w_i \le 1\,000\,000$
• For all $i, j$ with $1 \le i < j \le N$: $p_i \neq p_j$