Fair Coin Partition

Bessie and Canmuu found a sack of \(N\) gold coins. Each coin \(i\) has a value \(v_i\) (with \(1 \le v_i \le 2000\)). They want to split the coins into two piles as fairly as possible – that is, such that the absolute difference between the total values of the two piles is minimized. If an even split is not possible, then Bessie will receive the higher-valued pile.

In addition, there may be more than one way to obtain an optimal split. When the coins can be split evenly (i.e. the difference is zero), each unique partition is counted only once (the two piles are considered unordered). However, when the split is uneven the partition is determined by assigning Bessie the pile with the higher sum, so only one of the two complementary subsets is valid.

Your task is to compute the minimum possible difference between the two piles, and count the number of ways to achieve that optimal split.

inputFormat

The first line contains a single integer \(N\) \((1 \le N \le 250)\), the number of coins.

The second line contains \(N\) space-separated integers \(v_1, v_2, \ldots, v_N\) \((1 \le v_i \le 2000)\), representing the value of each coin.

outputFormat

Output two integers separated by a space: the smallest possible difference between the two piles, and the number of ways to achieve that difference.

sample

4
1 1 1 1

0 6