Sức Chịu Của Bàn

Bối cảnh

Bạn có \( N \) chân bàn, mỗi chân có sức chịu đựng khác nhau. Chân bàn \( i \) có thể chịu được trọng lượng \( W_i \), và sẽ bị gãy nếu phải chịu trọng lượng lớn hơn.

Yêu cầu

Bạn muốn xây dựng một cái bàn sử dụng một số chân bàn không rỗng. Khi bạn đặt một trọng lượng lên bàn, trọng lượng này sẽ được phân phối đều cho tất cả các chân bàn.

Ví dụ, nếu bạn xây dựng một cái bàn với 4 chân, và đặt một trọng lượng 18 lên nó, mỗi chân sẽ phải chịu trọng lượng \( \frac{18}{4} = 4.5 \) . Do đó, một cái bàn với các chân có sức chịu đựng [ 4, 4, 5, 6] sẽ không thể chịu được trọng lượng này (hai chân với sức chịu đựng 4 sẽ gãy), trong khi một cái bàn với các chân có sức chịu đựng [5,6,6,8] sẽ có thể chịu được.

Tìm trọng lượng tối đa mà một cái bàn được xây dựng từ một số chân bàn có thể chịu được mà không bị gãy.

Lưu ý: Các tập hợp con không cần phải liên tiếp: ví dụ, [1,3] là một tập con của [1,4,3,2].

Input

Dòng đầu tiên của đầu vào sẽ chứa một số nguyên \( T \), đại diện cho số lượng test case. Mỗi test case bao gồm hai dòng:

• Dòng đầu tiên của mỗi test case chứa một số nguyên \( N \), số lượng chân bàn bạn có.
• Dòng tiếp theo chứa \( n \) số nguyên cách nhau bởi dấu cách \( W_1, W_2, \ldots, W_N \), đại diện cho sức chịu đựng của mỗi chân bàn.

Output

Đối với mỗi test case, xuất trên một dòng mới trọng lượng tối đa mà bàn có thể chịu được khi sử dụng một số chân bàn không rỗng.

Ràng buộc

• \( 1 \leq T \leq 20000 \)
• \( 1 \leq n \leq 200000 \)
• \( 1 \leq w[i] \leq 10000 \)

Đảm bảo rằng tổng số chân bàn qua tất cả các test case sẽ không vượt quá \( 200000 \).

Ví dụ 1

Input

2
3
1 2 3
4
2 2 10 3

Output

4
10

Giải thích ví dụ

• Test case 1: Có bảy tập hợp con không rỗng của các chân bàn. Hãy xem xét từng tập hợp:

  [1] - trọng lượng tối đa là 1.
  [2] - trọng lượng tối đa là 2.
  [3] - trọng lượng tối đa là 3.
  [1,2] - không thể chịu trọng lượng 3 hoặc lớn hơn vì
  3/2 = 1.5 > 1, nhưng 2 là có thể.
  [1,3] - không thể chịu trọng lượng 3 hoặc lớn hơn, nhưng 2 là có thể.
  [2,3] - không thể chịu trọng lượng 5 hoặc lớn hơn, nhưng 4 là có thể.
  [1,2,3] - không thể chịu trọng lượng 4 hoặc lớn hơn, nhưng 3 là có thể.
  
  Vậy là tốt nhất là chọn hai chân, cụ thể là [2, 3]: trọng lượng tối đa mà bàn có thể chịu được là 4.

Thông tin học tập

• Buổi: B16
• Concepts: sorting, greedy group selection
• Giới hạn kiến thức: B01-B16
• Time limit: 2 seconds
• Memory limit: 64 MB
• Point: 15