题目描述

一群小矮人掉进了一个很深的陷阱里，由于太矮爬不上来，于是他们决定搭一个人梯。即：一个小矮人站在另一小矮人的 肩膀上，直到最顶端的小矮人伸直胳膊可以碰到陷阱口。

对于每一个小矮人，我们知道他从脚到肩膀的高度 $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$。

输出格式

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

2
20 10
5 5
30

2

2
20 10
5 5
35

1

提示

对于 $30\%$ 的数据，$N\leq 200$；

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