题目背景

又是一个丰收的秋日，穰子家有好几块红薯地，每块地的红薯需要不同时间采摘，且每块地有「采摘截止时间」（超过时间的话红薯就会坏在地里），这个秋日，穰子想要尽可能多的收集红薯。

题目描述

穰子从家出发，只能按「从近到远」的顺序去地块，求能采摘到的最多红薯数量，且总耗时不超过所有地块的截止时间之和。

输入格式

第一行：n（红薯地块数，1≤n≤15）。 接下来 n 行：每行两个整数 ti（采摘第 i 块地的耗时，1≤ti≤10）、di（第 i 块地的截止时间，1≤di≤50） 穰子必须按「地块编号从小到大」的顺序选择是否采摘。

输出格式

能采摘到的最多红薯数量

样例

4
2 5
3 8
1 6
4 15

3

样例解释

最优选择：摘第 1、3、4 块地。 总耗时：2+1+4=7 ≤ 所有截止时间（5/6/15）， 数量：3（摘第 1/2/3 块的话，总耗时 2+3+1=6，但第 2 块截止时间 8≥6，数量也是 3；两种选法都得 3）。