[TJOI2013] 拯救小矮人

题目描述

一群小矮人掉进了一个很深的陷阱里,由于太矮爬不上来,于是他们决定搭一个人梯。即:一个小矮人站在另一小矮人的 肩膀上,直到最顶端的小矮人伸直胳膊可以碰到陷阱口。 对于每一个小矮人,我们知道他从脚到肩膀的高度 $A_i$,并且他的胳膊长度为 $B_i$。陷阱深度为 $H$。 如果我们利用矮人 $1$,矮人 $2$,矮人 $3$,……,矮人 $k$ 搭一个梯子,满足 $A_1+A_2+A_3+\dots+A_k+B_k \geq H$,那么矮人 $k$ 就可以离开陷阱逃跑了,一旦一个矮人逃跑了,他就不能再搭人梯了。 我们希望尽可能多的小矮人逃跑,问最多可以使多少个小矮人逃跑。

输入输出格式

输入格式


第一行一个整数 $N$,表示矮人的个数,接下来 $N$ 行每一行两个整数 $A_i$ 和 $B_i$,最后一行是 $H$。

输出格式


一个整数表示最多可以逃跑多少小矮人。

输入输出样例

输入样例 #1

2
20 10
5 5
30

输出样例 #1

2

输入样例 #2

2
20 10
5 5
35

输出样例 #2

1

说明

对于 $30\%$ 的数据,$N\leq 200$; 对于 $100\%$ 的数据,$1 \leq N\leq 2000$,$1 \leq A_i,B_i,H\leq10^5$。