问题 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 next n lines each contains two numbers ai,bi (0 <= ai, bi <= 1,000), representing the number of boys and girls in the group.
输出
样例输入 复制
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