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.