YASSP - Yet Another Subset Sum Problem

Let Y be an array of integers of size N.

Let G(x) be a set comprising of the size of all the subsets of the array Y whose sum is x.

Let F(G(x)) denote the number of unique elements in the set G(x).

Your task is to find the maximum value of F(G(x)) and the corresponding value x for the given array Y.

If multiple 'x' correspond to maximum F(G(x)), print the smallest one.

Input

The first line describes the number of test cases T.

The input contains several test cases, each one described in exactly two lines.

The first line contains an integer N indicating the number of elements in the array.

The second line contains N integers separated by single spaces, representing the elements of the array.

Output

For every test case, print two integers: maximum F(G(x)) and the minimum value of x corresponding to it.

Constraints

T <= 50
1 <= N <= 50
1 <= Y[i] <= 1000

Example

Input:
2
4
1 2 3 4
6
3 2 3 4 5 3

Output:
2 3
2 5

Explanation

For test Case 1

  • G(1) : {1} and F(G(1)) : 1.
  • G(2) : {1} and F(G(2)) : 1.
  • G(3) : {1,2} and F(G(3)) : 2.
  • G(4) : {1,2} and F(G(4)) : 2.
  • G(5) : {2,2} and F(G(5)) : 1.
  • G(6) : {2,3} and F(G(6)) : 2.
  • G(7) : {2,3} and F(G(7)) : 2.
  • G(8) : {3} and F(G(8)) : 1.
  • G(9) : {3} and F(G(9)) : 1.
  • G(10): {4} and F(G(10)) : 1.

Added by:utk1369
Date:2014-09-16
Time limit:1s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem

hide comments
2014-09-21 16:49:37 Martijn Muijsers
@Jacob Plachta I have not solved this problem yet, but from what I can reason:

There is 1 subset with sum 0, namely {}, so if there are no 2 subsets with some sum k, then x = 0 should be the correct answer, since then F(G(0)) = 1 (which is the largest), and x = 0 is the smallest x.

RE (Jacob): Yeah, but as I said, x=0 is apparently not valid.

Last edit: 2014-09-30 06:52:04
2014-09-19 14:49:29 Jacob Plachta
Apparently x must be a positive integer, not 0.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.