{"raw_statement":[{"iden":"statement","content":"Teamwork is highly valued in the ACM ICPC. Since the beginning, the ICPC has distinguished itself from other programming contests in that teamwork is a key factor.\n\nThe University of Beijing, host of next year's World Finals, is planning recreational activities for the participants. They want to prepare games that show the importance of teamwork and enable new acquaintances among the contestants from all over the world. One of the staff members has been thinking about the following game.\n\nIn a court we have several N-person teams. The goal of each team is roughly as follows: starting from a corner, each team must take all of its members to the other corner of the court. The winning team is the one that finishes this in the shortest time.\n\nNow we explain the game more formally. Consider the team that starts at corner A and must take all of its members to corner B. The following procedure is repeated:\n\nThe organization wants to form the teams so that no team has an advantage. They entrusted you with the following task. Given the time in seconds that the members of a team take to go from a corner to the other, find the minimum time it takes for the team to take all its members from corner A to corner B. When two team members cross the court with their legs tied, the time for the pair to cross is the maximum between the times of the two members.\n\nThe first line of input contains an integer N, the number of team members. The next line contains N integers ti, the time in seconds that the i-th team member takes to go from one corner to the other.\n\nPrint a single integer, the minimum time required for the whole team to reach corner B.\n\nIn the first example, the process can be completed in 120 seconds as follows:\n\nThis is not the only way to complete the process in this total time, but no other way does it in strictly less than 120 seconds.\n\n"},{"iden":"input","content":"The first line of input contains an integer N, the number of team members. The next line contains N integers ti, the time in seconds that the i-th team member takes to go from one corner to the other.  1 ≤ N ≤ 105  1 ≤ ti ≤ 109 "},{"iden":"output","content":"Print a single integer, the minimum time required for the whole team to reach corner B."},{"iden":"examples","content":"Input330 40 50Output120Input410 20 50 100Output170"},{"iden":"note","content":"In the first example, the process can be completed in 120 seconds as follows:  The first and second members go from A to B in 40 seconds.  The first member returns to corner A in 30 seconds.  The first and third team members go from A to B in 50 seconds. This is not the only way to complete the process in this total time, but no other way does it in strictly less than 120 seconds."}],"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 $ i \\in \\{1, \\dots, T\\} $:  \n- Let $ n_i \\in \\mathbb{Z} $ denote the number of cars to manufacture.  \n- Let $ k_i \\in \\mathbb{Z} $ denote the number of stages per car.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 1000 $  \n2. For each $ i \\in \\{1, \\dots, T\\} $:  \n   - $ 1 \\le n_i \\le 10^9 $  \n   - $ 1 \\le k_i \\le 10^9 $  \n\n**Objective**  \nFor each test case $ i $, compute the minimum number of days required to complete all $ n_i $ cars, given that:  \n- Each car must pass through $ k_i $ stages, one per day.  \n- On day $ d $, up to $ \\min(d, n_i) $ cars can be in the pipeline, with each car advancing to the next stage if possible.  \n- A car is completed when it finishes stage $ k_i $.  \n\nThe total days required is:  \n$$\n\\boxed{n_i + k_i - 1}\n$$","simple_statement":"You need to build n cars, each requiring k stages. Each day, every car moves to the next stage, and a new car starts at stage 1. How many days to finish all n cars?","has_page_source":false}