Agent#403
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 partners—one older and one younger—but these two are not partners with each other. In groups of 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.
The input begins with an integer (1 \leq M \leq 13), representing the number of groups in which Bond is teaching. Following this are group descriptions. Each group description consists of two lines: the first line contains an integer , the number of agents in the group (2 \leq N \leq 10000). The second line lists pairs of positive integers. Each pair consists of the agent's age in days (ranging from to ) and their risk of exposure (ranging from to ). All agents in a group have distinct ages.
For each group, output a single number on a separate line—the minimum total risk of exposure for that group.
Example 1
Example Explanation: In the first group, the only possible pairing is - (risk ) and - (risk ).
In the second group, the agents and , being the oldest and youngest, must pair with and , respectively. The agent can choose between or as a partner. Pairing with results in a lower risk ( versus ), leading to an optimal total risk of 1 + 2 + 4 = 7.