P5364: 千层背包
传统题
1.000s
时间限制
256MB
内存限制
1 提交
1 解决
【题目描述】
题目背景
有时，打开一个包，会发现其中还有另一个包，再打开，会发现其中还有更小的包，我们称这样的现象为套包。
题目描述
有 n
种不同规格的包，每种包有两个参数，外径由 ai
表示，内径由 bi
表示。在一个包 x 的内部，可以放置一些更小的包，只要这些小包的外径之和小于或等于 x 的内径即可。
每一种包的数量是任意多的，现在小爱只能背一个背包出门，但她可以通过套包的方式增加携带背包数量，请你求出这个最大数量。
输入格式
第一行：单个正整数 n。
第二行到第 n+1
行：每行两个正整数表示 ai
和 bi
。
输出格式
单个整数：表示最大携带背包数量。
数据范围
对于 50 % 的数据：1≤n≤50
，1≤bi<ai≤10
3
对于 100 % 的数据：1≤bi<ai≤10
5
样例数据
输入:
3
200 120
50 40
20 10
输出:
8
说明:
1
号背包可以套两个2号背包和一个3号背包，每个2号背包又可以套两个3号背包