Agent
Agent James Bond, though retired, still craves new adventures. Thus, he eagerly accepted the opportunity to teach a master class at the "Young Agent" school. One of the classes focuses on teamwork, emphasizing the importance of having a reliable partner in the intelligence field. Partners must be as close in age as possible, meaning two agents cannot be partners if there is a third agent whose age falls between theirs.
Bond's challenge is to pair agents so that each has at least one partner. Each agent can have up to two partners—one older and one younger—but these two are not partners with each other. In groups of four or more agents, there are multiple ways to form partnerships.
After several sessions, Bond evaluated the agents' skills and assessed the risk of exposure for each one. In a partnership, only the older agent is at risk. Therefore, the goal is to pair agents in a way that minimizes the total risk for the group.
Input
The input begins with an integer M (1 <= M <= 13), representing the number of groups in which Bond is teaching. Following this are M group descriptions. Each group description consists of two lines: the first line contains an integer N, the number of agents in the group (2 <= N <= 10000). The second line lists N pairs of positive integers. Each pair consists of the agent's age in days (ranging from [5000, 16000]) and their risk of exposure (ranging from [1, 1000]). All agents in a group have distinct ages.
Output
For each group, output a single number on a separate line—the minimum total risk of exposure for that group.
Example Explanation: In the first group, the only possible pairing is 6000-5500 (risk 2) and 5500-5000 (risk 3).
In the second group, the agents 5005 and 5001, being the oldest and youngest, must pair with 5004 and 5002, respectively. The agent 5003 can choose between 5004 or 5002 as a partner. Pairing with 5004 results in a lower risk (2 versus 3), leading to an optimal total risk of 1 + 2 + 4 = 7.