# 问题 U: Fantasy Festival

#### 题目描述

There are n groups of friends who want to join the Fantasy Festival, where the ith group contains ai boys and bi girls.

For each group of friends, either all or none of this group can join the Fantasy Festival. In other words, it's not allowed to let only part of a group of friends join, while the other part not join. For example, if LBH,LMK,CGP are a group of friends, we only have two choices:
- All of LBH,LMK,CGP join (3 people)
- None of LBH,LMK,CGP join (0 people)

Now we need to arrange several groups of friends to attend the Fantasy Festival (at least one group). Assume that they are not gay or les and are willing to partner with the opposite sex. To let the activity on Fantasy Festival more interesting, we plan to select several groups of these friends (at least one group) so that the difference between the number of boys and the number of girls is the smallest. This difference is called the number of single dogs.

In particular, if there are multiple choices to minimize the number of single dogs, the one with the most groups of friends should be selected. Note that we need to maxmize the number of groups, not the number of people!

Now please find out the best solution, that is, on the basis of minimizing the number of single dogs, make the number of groups as many as possible.

#### 输入

The first line contains a positive integer n(n <= 35), representing the number of groups of friends.

The next n lines each contains two numbers ai,bi (0 <= ai, bi <= 1,000), representing the number of boys and girls in the group.

#### 输出

Two positive integers, separated by a space. The first is the minimum number of single dogs. The second is maximum number of groups that can be selected based on the minimum number of single dogs.

3
2 5
8 4
1 9

1 2

5
7 4
8 9
10 2
1 5
10 11

1 3

### [The explaination of Sample 1]

In order to minimize the number of single dogs, the group {1,2} were selected, with 2+8=10 boys and 5+4=9 girls. The number of single dogs is 1.

### [The explaination of Sample 2]

Selecting group {2},{5},{1,4},{1,2,5} can all make the number of single dogs to be the least, which is . However, this question requires that the number of selected groups should be the most based on this, so the last situation is the best.