题目描述

迈克尔收到一份生日礼物，里面有n个积木块。每个积木块由两个参数(l, m)表示，其中上表面左侧有l个凸起的旋钮，中间有m个凸起的旋钮；对应的下表面左侧有l个凹陷的槽，中间有m个凹陷的槽。

积木块的叠放规则是：一个(l, m)积木块可以叠在另一个(l', m')积木块上，当且仅当 l ≥ l' 且 m ≥ m'。

问题要求：给定n个积木块，找出能叠出的最高高度的积木塔，并计算有多少种不同的积木组合可以达到这个最高高度。

输入格式

• 每组输入以整数n开头（n ≤ 10000），随后n行每行包含两个整数li和mi（1 ≤ li, mi ≤ 100），表示第i个积木块的参数。
• 输入以n=0结束。

输出格式

• 对每组输入，输出能叠出的最高积木塔的组合数。
• 所有输出结束后，输出一个单独的星号*。

输入示例 1

3  
3 2  
1 1  
2 3  
5  
4 2  
2 4  
3 3  
1 1  
5 5  
0  

输出示例 1

2  
3  
*  

来源

亚洲高雄竞赛 2003