{"raw_statement":[{"iden":"statement","content":"There are three islands named A, B, and C which are located at the corners of an equilateral triangle. There are $n$ visitors initially on island A. Each of the visitors has a destination island $w_i$ which is either island B or island C. There is one ferry boat currently docking at island A. The ferry boat has a fixed route: $A arrow.r B arrow.r C arrow.r A arrow.r B arrow.r C arrow.r A \\\\dots$\n\nEach visitor has an attribute $t_i$, representing the minimal time to ferry them between any two islands without causing seasick. The ferry boat can carry no more than three people at the same time. To ensure that all people on the boat won't be seasick, the time it takes voyaging between any two islands is determined by the largest $t_i$ of the people on the ferry boat.\n\nOnce a visitor arrives at the destination island, the visitor will stay on the island and will not embark on the ferry boat again. Besides, a visitor will only disembark from the ferry boat when arriving at his or her destination. The ferry boat can not set out from the dock if there is nobody on the boat, but luckily we have countless sailors on island A at the beginning. The sailors are so well trained that their attributes are all $1$, and unlike the visitors, they have no destination and can visit each island multiple times.\n\nAll sailors and the ferry boat should be back to island A after sending all visitors to their destination islands. You need to find out the shortest time to achieve this goal.\n\nThe first line of the input gives the number of test cases, $T$ ($1 <= T <= 10$). $T$ test cases follow.\n\nFor each test case, the first line contains an integer $n$ ($1 <= n <= 50000$), representing the number of visitors.\n\nIn the following $n$ lines, each line contains two integers describing a visitor. The first integer $w_i$ represents the visitor's destination island, where $w_i$ is either $1$ representing island B, or $2$ representing island C. The second integer $t_i$ ($1 <= t_i <= 1000$) represents the minimal time to ferry the visitor between any two islands.\n\nFor each test case, output one line containing \"_Case #x: y_\", where _x_ is the test case number (starting from $1$) and _y_ is the shortest time to send every visitors to the island they want to reach.\n\n"},{"iden":"input","content":"The first line of the input gives the number of test cases, $T$ ($1 <= T <= 10$). $T$ test cases follow.For each test case, the first line contains an integer $n$ ($1 <= n <= 50000$), representing the number of visitors.In the following $n$ lines, each line contains two integers describing a visitor. The first integer $w_i$ represents the visitor's destination island, where $w_i$ is either $1$ representing island B, or $2$ representing island C. The second integer $t_i$ ($1 <= t_i <= 1000$) represents the minimal time to ferry the visitor between any two islands."},{"iden":"output","content":"For each test case, output one line containing \"_Case #x: y_\", where _x_ is the test case number (starting from $1$) and _y_ is the shortest time to send every visitors to the island they want to reach."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n \\in \\mathbb{Z} $ be the number of visitors.  \n- Let $ W = (w_1, \\dots, w_n) $, where $ w_i \\in \\{1, 2\\} $, denote the destination island of visitor $ i $ (1 = B, 2 = C).  \n- Let $ T_v = (t_1, \\dots, t_n) $, where $ t_i \\in \\mathbb{Z} $, $ 1 \\le t_i \\le 1000 $, denote the sea-sickness threshold of visitor $ i $.  \n- Let $ S = \\{ s_j \\mid s_j = 1 \\} $ be an infinite multiset of sailors, each with threshold 1.  \n\nThe ferry follows the cyclic route: $ A \\to B \\to C \\to A \\to \\cdots $.  \nThe ferry capacity is 3.  \nTravel time between any two consecutive islands is $ \\max\\{ t_i \\mid \\text{visitor } i \\text{ is on board} \\} \\cup \\{1\\} $.  \nA visitor disembarks only upon reaching their destination and does not reboard.  \nThe ferry must start and end at island A, and must be empty at the end.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 10 $  \n2. $ 1 \\le n \\le 50000 $  \n3. $ w_i \\in \\{1, 2\\} $, $ 1 \\le t_i \\le 1000 $ for all $ i \\in \\{1, \\dots, n\\} $  \n\n**Objective**  \nMinimize the total time to transport all visitors to their destinations and return the ferry (and all sailors) to island A.","simple_statement":"You have three islands A, B, C in a triangle.  \nn visitors start at A, each wants to go to B or C.  \nEach visitor i has a time cost t_i — the ferry must wait this long between islands if they’re on board.  \nThe ferry holds at most 3 people.  \nFerry route: A → B → C → A → B → C → ...  \nSailors (with t=1) are everywhere and can help drive the boat.  \nAfter dropping everyone, the ferry and all sailors must return to A.  \nMinimize total time.","has_page_source":false}