루루의 과수원에는 그루의 사과나무가 있다.
과수원에서는 번부터 번까지 총 가지 품종의 사과를 기른다. 번 품종의 사과 하나의 가치는 이며, 한 나무에는 각 품종의 사과가 최대 하나씩 열려 있다.
루루는 사과를 수확하기 위해 다음 작업을 반복할 수 있다.
루루는 더 이상 작업을 할 수 없을 때까지 사과를 수확하려고 한다.
수확하는 순서에 따라 마지막에 각 나무에 남아 있는 사과가 달라질 수 있다. 루루는 수확 순서를 적절히 정하여, 마지막에 한 나무에 남아 있는 사과들의 가치의 합을 가능한 한 크게 만들고 싶다.
처음 각 나무에 열려 있는 사과들의 가치의 합이 주어질 때, 루루가 만들 수 있는 값의 최댓값을 구해 보자.
첫째 줄에 테스트 케이스의 수 가 주어진다. ()
각 테스트 케이스는 다음과 같이 주어진다.
첫째 줄에 사과나무의 수 이 주어진다. ()
각 테스트 케이스마다, 모든 수확이 끝난 뒤 한 나무에 남아 있는 사과들의 가치의 합으로 가능한 최댓값을 한 줄에 출력한다.
둘째 줄에 개의 정수 이 공백으로 구분되어 주어진다. 는 처음에 번째 나무에 열려 있는 사과들의 가치의 합을 의미한다. ()
모든 테스트 케이스에 대한 의 합은 이하이다.
