PKU 2291. Rotten Ropes

썩은 밧줄

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 4023	Accepted: 2620

설명

어떤 무거운 물체를 들어올리기 위해서 같은 길이인 n 개의 밧줄이 있다고 생각해봅시다. 이 때 각 밧줄들과 연결시켜 물체를 들어올리기 때문에 각 밧줄이 버틸수 있는 무게인 t 를 넘는 물건을 들어올리려고 하면 밧줄은 끊어집니다. 그러나 우리는 무거운 물체를 여러 개의 밧줄로 평행하게 묶어서 모든 밧줄을 끌어올리는 방법을 쓰면 무거운 물체도 들어올릴 수 있습니다. w 의 무게를 가진 무거운 물건을 들어올리기 위해 k 개의 밧줄을 사용한다면, 각 밧줄에 w/k 만큼의 무게가 주어진다고 가정합니다. 하지만 밧줄이 버틸수 있는 무게인 t 를 놓고 볼 때, w/k > t 가 된다면 밧줄은 끊어지게 됩니다. 예를 들어 3 개의 밧줄이 각각 버틸수 있는 무게가 1, 10, 15 라고 치면, 3 보다 무거운 무게를 가진 물건을 이 3 개의 밧줄을 묶어서 들어올리려 할 경우 가장 약한 밧줄이 끊어지기 때문에 3개의 밧줄을 전부 묶어서 들어올릴 수 없습니다. 그러나 두번째 밧줄은 그 자체만으로 10의 무게까지 들어올릴 수 있습니다. 각 밧줄이 버틸 수 있는 무게를 알려주면 당신은 주어진 밧줄들의 부분집합을 하나 골라서, 부분집합에 속한 밧줄들이 하나도 끊어지지 않고 물건을 들어올릴 수 있는 가장 무거운 무게를 알아내는 것입니다.

입력

입력의 첫 번째 줄은 하나의 정수 t (1 <= t <= 10) 를 쓰는데 뒤에 나올 테스트 케이스들의 개수를 나타냅니다. 각 테스트 케이스들의 첫 번째 줄은 하나의 정수 n (1 <= n <= 1000) 을 입력하는데, 이 n 은 밧줄의 개수를 나타냅니다. 그 다음으로 나오는 줄에는 1부터 10000까지의 범위 안에 있는 n 개의 정수들이 나오는데 각각은 밧줄이 끊어지지 않는 최대한의 무게를 나타내고, 각 무게들은 사이에 공백으로 띄어서 나타냅니다.

출력

테스트 케이스에서 주어진 밧줄들이 하나도 끊어지지 않는 최대한의 무게를 한 줄로 출력합니다.

입력 예시

2
3
10 1 15
2
10 15

출력 예시

20
20

Source

Tehran 2003

p.s: 일부분 수정했습니다.