MAXSUB - Maximum Subset of Array

Given an array find the sum of the maximum non-empty subset of the array and also give the count of the subset. A subset of an array is a list obtained by striking off some (possibly none) numbers.

A non-empty subset implies a subset with at least 1 element in it.

Input

First line contains an integer T which is the number of integers. Following this T-cases exist.

Each case starts with a line containing an integer n which is the number of elements in the array.

The next line contains n-integers which contain the value of this subset.

Constraints

T <= 20

n <= 50,000

Each element in the array <= 1,000,000,000

Output

For each test case output the value of the maximum subset and the count of the subsets modulo 1000,000,009

Example

Input:
2
5
1 -1 1 -1 1
6
-200 -100 -100 -400 -232 -450

Output:
3 1
-100 2

Added by:.:: Pratik ::.
Date:2011-03-07
Time limit:0.507s-2.450s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2011-03-09 13:44:49 :D
"count of the subset" means the number of different subsets that have minimal sum, not the number of subsets elements.
2011-03-09 12:29:26 .:: Pratik ::.
This is a very trivial problem. Should I move to tutorial, or anybody has an idea for challenge? (Lowest source code)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.