PKU 2636. Electrical Outlets

전기 콘센트

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 3730	Accepted: 2806

설명

Roy는 새 아파트로 막 이사왔다. 아파트는 사실 새 것은 아니고, 집에 전기가 들어오지 않는 시대로 거슬러 올라간 것처럼 착각할 수 있는 상태이다. Roy의 아파트는 벽붙이형 콘센트가 단 하나뿐이기 때문에 Roy는 그의 가전제품을 한번에 하나씩만 전원을 공급할 수 있다.
Roy는 컴퓨터로 일하면서 동시에 TV를 보는 것을 좋아하고, 청소를 하면서 HiFi system 을 큰 소리로 듣는 것을 좋아하기 때문에, 하나의 콘센트만 사용하는 것은 기능이 아니다. 사실 그는 그의 모든 가전제품을 동시에 전부 콘센트에 꽂기를 원한다. 해답은 당연히 power strips이고 Roy는 옛 아파트에서 쓰던 오래된 것들을 찾았다. 그러나 옛날에 살던 아파트는 더 많은 벽붙이형 콘센트가 있었기 때문에, 그는 그의 power strips의 콘센트 개수가 충분한지 불확실하다.
당신의 임무는 Roy가 주어진 power strips의 집합에 따라, 가전제품에 얼마나 많은 전기를 공급해줄 수 있는지 계산하는 것을 돕는 것이다. power strips가 없다면 단 하나의 전기제품만 연결할 수 있다는 것을 알아두자. 또한 power strip은 어떻게 사용하든 전기가 들어오는 것 역시 기억해두자.

입력

입력은 하나의 정수 1<=N<=20 으로부터 시작하는데, 뒤에 나오는 테스트 케이스의 개수를 나타낸다. N 행의 뒤로 테스트 케이스가 나온다. 각 테스트 케이스는 정수 1<=K<=10 으로 시작하는데 각 테스트 케이스의 power strips의 개수를 나타낸다. 그 뒤로 같은 줄에 한 칸의 공백을 두고 O1 O2 ... OK, 2<=Oi<=10 으로, 각 power strip에 있는 콘센트의 개수를 나타낸다.

출력

출력은 한 테스트 케이스당 하나의 줄로 나오는데, 전원을 연결할 수 있는 가전제품의 최대치가 나온다.

입력 예시

3
3 2 3 4
10 4 4 4 4 4 4 4 4 4 4
4 10 10 10 10

출력 예시

7
31
37

Source

Nordic 2005

역자 주 : Power strip = 멀티탭

p.s: Lonewolf dlbo 군의 의견을 들어 test case 의 번역단어를 수정합니다.