진귀한 별미

시간 여행은 몹시 피곤한 일이라 금세 배가 고파집니다. 다행히 시대마다 공룡 고기, 도도새 알, 매머드 우유처럼 진귀한 별미가 가득합니다. 하지만 타임머신에는 냉장고를 실을 공간이 없어서, 팀이 어떤 별미를 먹으려면 그 자리에서 바로 먹어야 합니다. 그런데 한 번 먹으면 너무 배가 불러, 바로 다음 시대에서는 아무것도 먹을 수 없습니다. 각 음식에는 팀이 매긴 가치가 있으며, 목표는 실제로 먹는 음식들의 가치 합을 최대로 만드는 것입니다. 시대를 방문하는 순서는 이미 정해져 있어 바꿀 수 없습니다. 어떤 음식을 먹을지 골라서 얻을 수 있는 가치 합의 최댓값은 얼마일까요?

첫째 줄에 데이터 집합의 개수 $K$가 주어집니다. 이어서 $K$개의 데이터 집합이 다음 형식으로 주어집니다. 각 데이터 집합의 첫째 줄에는 팀이 마주칠 음식의 개수 $n$이 주어지며, $1 \le n \le 50000$입니다. 다음 줄에는 음식의 가치를 나타내는 $n$개의 정수 $v_i$가 주어지며, $1 \le v_i \le 1000$입니다. 나열된 $v_i$의 순서는 팀이 음식을 마주치는 순서와 같습니다.

각 데이터 집합마다 먼저 Data Set x: 를 한 줄에 출력합니다. 여기서 $x$는 데이터 집합의 번호로 1부터 시작합니다. 다음 줄에는 팀이 얻을 수 있는 가치 합의 최댓값을 출력합니다. 서로 다른 데이터 집합 사이에는 빈 줄을 하나 넣어 구분합니다.