#753 뚱뚱한 수열

문제

题面语言

길이 $N$ 인 수열 $A = [A_1, A_2, \cdots, A_N]$ 이 주어진다.

인덱스 $1 \leq i_1 < i_2 < \cdots < i_k \leq N$ 을 골라 만든 수열 가 를 만족하면, 이 수열을 의 이라고 한다. 이 수열의 길이는 이다.

$A$ 의 증가하는 부분수열 중 길이가 가장 긴 것들을 생각하자. 그중 원소의 합이 가장 큰 것을 $A$ 의 뚱뚱한 수열이라고 한다.

$A$ 의 뚱뚱한 수열과 그 원소의 합을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ case $_1$ case $_2$

각 테스트 케이스마다 다음 두 줄을 출력한다.

첫째 줄에 $A$ 의 뚱뚱한 수열의 원소를 앞에서부터 차례대로 공백으로 구분하여 출력한다.

둘째 줄에 $A$ 의 뚱뚱한 수열의 원소의 합을 출력한다.

가능한 답이 여러 가지라면 아무거나 출력해도 된다.

#	分数	数据范围
1	8	$N \leq 10$ . 모든 테스트 케이스에 대한 $N$ 의 합은 $10\,000$ 이하이다.
2	22	$N \leq 5\,000$ .

样例输入

4
6
10 20 10 30 20 50
7
3 1 4 1 5 9 2
5
5 5 4 4 3
1
1000000000

样例输出

10 20 30 50
110
3 4 5 9
21
5
5
1000000000
1000000000

첫 번째 케이스에서 가장 긴 증가하는 부분수열은 $[10, 20, 30, 50]$ 하나뿐이다.

두 번째 케이스에서 가장 긴 증가하는 부분수열의 길이는 $4$ 이며, $[3, 4, 5, 9]$ 와 가 있다. 원소의 합은 각각 과 이다.