巧接人参果
时间限制: 1 Sec 内存限制: 128 MB
提交: 270 解决: 61
[提交] [状态] [讨论版] [命题人:admin]
题目描述
唐僧率领徒弟孙悟空、猪八戒、沙和尚去西天取经,路经万寿山五庄观。 观主镇元大仙上天听道去了,临行嘱咐童子,大唐高僧路经此地,可取人参果好生款待。这人参果乃仙家之宝 ,食之能长生不老。师徒一行来到五庄观,观中童儿只将人参果款待唐僧 。悟空不甘受此冷落,加之贪吃的八戒在旁怂恿,便潜入果园偷吃人参仙果。 恰巧你也在那,于是你有缘与孙悟空一起摘人参果。不过这人参果遇金则落,遇土则遁。为此,孙悟空、猪八戒、沙和尚三人爬上果树用金箍棒等将人参果打落,而你则在树底下接人参果。 这人参果别处都不掉,就掉落在他身旁的10米范围内。人身果如果掉在了地上就不见了。当然你很聪明,可是看到这么多人身果,动作也变迟钝了,每秒种只有在移动不超过一米的范围内接住坠落的人身果。现在给你接人参果如图标上坐标: 为了使问题简化,假设在接下来的一段时间里,人参果都掉落在0-10这11个位置。开始时你站在5这个位置,因此在第一秒,他只能接到4,5,6这三个位置中期中一个位置上的馅饼。问你最多可能接到多少个人参果?(假设背包可以容纳无穷多个人参果)
输入
输入数据有多组。每组数据的第一行为以正整数n(0 < n < 100000),表示有n个人参果掉下来。在接下来的n行中,每行有两个整数x,T(0 <= T < 100000),表示在第T秒有一个人参果掉在x点上。同一秒钟在同一点上可能掉下多个人身果。n=0时输入结束。
输出
每一组输入数据对应一行输出。输出一个整数m,表示你最多可能接到m个人参果。
样例输入
6
5 1
4 1
6 1
7 2
7 2
8 3
0
样例输出
4