# 问题 U: Fantasy Festival

#### 题目描述

There are **n** groups of *friends* who want to join the Fantasy Festival, where the i^{th} group contains a_{i} boys and b_{i} 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.**

#### 输入

**n(n <= 35)**, representing the number of groups of

*friends*.

The next

**n**lines each contains two numbers

**a**

_{i}

**,b**

_{i}

**(0 <= a**

_{i}

**, b**

_{i}

**<= 1,000)**, representing the number of boys and girls in the group.

#### 输出

*number of single dogs*. The second is maximum number of groups that can be selected ba

#### 样例输入 复制

```
3
2 5
8 4
1 9
```

#### 样例输出 复制

`1 2`

#### 提示

### [Sample 2 input]

5 7 4 8 9 10 2 1 5 10 11

### [Sample 2 output]

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 $1$. However, this question requires that the number of selected groups should be the most ba