题目描述

给你一些整数，你要找出第n小的数，也就是说把数据按升序排序后，输出下标是n的那个数，注意，我们规定下标是从0开始的。但是我们给出的数据的格式比较奇怪，我们是按区间给出，例如：给出两个区间：【1,3】、【5,7】，那么代表的给出的数实际是{ 1, 2, 3, 5, 6, 7 }，注意，我们给出的区间可能有重叠部分。例如：给出两个区间：【1, 4】、【3, 5】，那么代表的给出的数实际是{ 1, 2, 3, 3, 4, 4, 5 }.

输入格式：

第一行，一个整数t,表示我们给出t个区间。1 <= t <= 50。

接下来有t行，每行有两个整数：x 和y，表示区间【x,y】，其中-2000000000<=x<=y<=2000000000。    

最后一行，一个整数n,表示求出第n小的，下标从0开始，0<=n<=所有区间代表的实际的整数的个数，且n<=2000000000。

输出格式：

一个整数，第n小的数。

输入样例：

输入样例1:

2

1 3

5 7

4

输入样例2

2

1  4

3  5

3

输出样例：

输出样例1

6

输出样例2

3

样例解释：

样例一解释：两个区间实际的数是：{1,2,3 ,5,6,7}

样例二解释：代表的给出的数实际是{ 1, 2, 3, 3, 4, 4, 5 }.