9053번 - Homework 다국어

Professor Bae teaches a class titled “Problem Solving” in Gyeryong University. In his class, the attendants discuss with each other about problems assigned as homework the day just before the class. Thus, the attendants should complete the homework just in one day.

Professor Bae, who is lazy, announces the homework problems to only one of the attendants and he wishes every attendant inform the homework via phone calls by each other. Fortunately, every attendant knows every other’s phone number. Each attendant, however, does not immediately broadcast this announcement of homework to others because every attendant is crazy for score, but informs others after completing the homework.

Assume that N students (s₁, s₂, …, s_N) are enrolled as the attendants of this strange class and s_i takes t_i hours to complete a homework assignment. Also, after a student completes the homework, he makes a phone call to students who have not been informed yet, one per every hour.

Write a program to compute the shortest time (in hours) for every attendant to complete homework under assuming the above.

For example, if Professor Bae announces a homework assignment to s₁ at 3 o’clock, where N = 3, t₁ = 1(hour), t₂ = 1 and t3 = 3, then s₁ completes his homework at 4 o’clock. If s₁ informs s₂ at 4 o’clock, then at 5 o’clock s₁ or s₂ can inform it to s₃ after s₂ completes the homework. Finally s₃ completes his homework at 8 o’clock. In this case it takes 5 hours for every attendant to complete the homework. But it can be completed in 4 hours if s₁ informs it to s₃ first at 4 o’clock. 

Your program is to read from standard input. The input consists of T test cases. The number of test cases T (1 ≤ T ≤ 20) is given in the first line of the input. The first line of each test case contains an integer N (1 ≤ N ≤ 10) which is the number of students. The next line contains N integers t₁, t₂, …, t_N (1 ≤ t_i ≤ 10). Assume that Professor Bae first announces his homework to s₁.

Your program is to write to standard output. Print exactly one line for each test case. The line should contain an integer that is time every student can complete homework in the shortest.