问题描述

呆子很喜欢玩算法,还记得当初上算法课的时候就被k选择问题给迷住了。对了,你知道k选择问题?
k选择问题是这样的:

给你n个整数,要你找出其中第k小的元素,比如6个整数:1 4 2 3 4 2,它的第0小元素是1,第1小
是2,第2小还是2,然后第3小是3,第4小和第5小元素都是4。

算法书上讲了很多很多的算法,有平均时间复杂度是线性的,也有最坏情况时间复杂度就是线性的,
呆子想啊,线性时间的算法应该是最好的了吧,这个问题应该研究的比较彻底了吧!

有一天,呆子碰到erwen,于是呆子给erwen大谈特谈自己的学习心得,然后说,恩,这个
问题已经研究得差不多了,没什么好玩的了,我要研究其他问题了。可是这个时候erwen若有所思
的说:“不是这样的吧,来,我给你出个问题!” 问题是这样的:

问题的输入仍然是一些整数,不过不再是简单列举出这些整数了,而是列出了一些区间,比如:
[1 2], [2 4], [4 4]
值得注意的是:这些区间都是闭区间,而且多个区间之间可能又重叠,比如上面的前两个区间。
另外上面的这个输入例子相当于输入的整数序列是: 1 2 2 3 4 4,也就是说一个整数在多少个区间
出现了,那么它就要出现多少次。

呆子想了想,yi!! 还真没有现成的算法也,不过呆子是个顽固的家伙,一定要找出一个现成的算法
来解决这个题目。erwen 可不这样想,erwen 想赶快搞出一个算法来打倒呆子,不过erwen很忙,你
能够帮助 erwen么?


输入描述

输入包含多组数据。

每组数据,首先是一个整数n,表示区间的个数,(1 <= n <= 100)。
然后是n行,每行两个整数,用一个空格隔开,分别是区间的开始a和区间的结束b,满足
   -2000000000 <= a <= b <= 2000000000。
然后是单独一行的一个整数k,表示要输出第k最小元素,这里 0 <= k <= 2000000000,我们保证
第k最小元素一定存在。


输出描述

每组输入输出一个整数,表示我们要求的元素,注意这个整数单独成行。


输入样例

3
1 2
2 4
4 4
3

输出样例

3

From:  daizisheng