github.com/captn3m0/codechef.git

---
languages_supported:
    - NA
title: A5
category: NA
old_version: true
problem_code: A5
tags:
    - NA
layout: problem
---
###  All submissions for this problem are available. 

**This problem was part of the [CodeChef April Challenge](http://www.codechef.com/APRIL09/). All user submissions for this contest problem are publicly available [here](http://www.codechef.com/APRIL09/status/A5/).**

Shaheen has bought some gifts for a friend, which are wrapped up in several boxes of different sizes (all of which are full). She will need to carry the gifts a long way to her friend's house, so she would prefer to add some extra packing, and accommodate everything in one extra box. Moreover, to avoid damaging the contents, she does not wish to place more than two boxes directly within any box; however, boxes can be placed within boxes which contain other boxes, etc. A box which is used for holding two boxes of sizes _a_ and _b_ will have size _a_+_b_, and will cost Shaheen _a_+_b_ coins at the local store. Please help Shaheen determine the minimum cost required to achieve the complete packing, and the number of different possible packings (arrangements of boxes within each other) having such a minimal cost.

### Input

The first line of input is _n_ <=2000, the number of boxes with Shaheen's gifts. The next _n_ lines of input contain one positive integer each, not greater than 106, representing the sizes of the successive boxes.

### Output

Print to output exactly 2 numbers separated by spaces: the cost of the optimal solution, and the number of distinct ways of achieving this solution (modulo 109).

### Example

<pre>
<b>Input:</b>
5
3
2
3
5
1

<b>Output:</b>
31 3
</pre>

**Explanation:**
The three solutions leading to cost 31 are as follows:/>

1\) pack the 2nd and the 5th box together, pack the resulting box together with the 1st box, and pack the result together with an additional box used for packing the 3rd and 4th boxes,

or

2\) pack the 2nd and the 5th box together, pack the resulting box together with the 3rd box, and pack the result together with an additional box used for packing the 1st and 4th boxes,

or

3\) pack the 2nd and the 5th box together, pack the resulting box together with the 4th box, and pack the result together with an additional box used for packing the 1st and 3rd boxes.