UOJ Logo

NOI.AC

1S 512MB

#704. 第K小的数

统计

题目描述

有个两个正整数区间$ l_1 \leq S_1 \leq r_1$和$l_2 \leq S_2 \leq r_2$ 现在请你找出这两个区间合并后第$K$小的正整数值。

输入格式

五个正整数$l_1,l_2,r_1,r_2,k $

输出格式

输出第$k$小的值

输入样例

1 5 4 8 2

输出样例

2

输入样例2

8886 6221 78097 91055 74492

输出样例2

44799

数据规模

对于全部数据$k$不超过两个区间长度之和

对于$30\%$的数据$1 \leq l_1,l_2 \leq r_1,r_2 \leq 10^5 $

对于$60\%$的数据$1 \leq l_1,l_2 \leq r_1,r_2 \leq 10^8 $

对于$100\%$的数据$1 \leq l_1,l_2 \leq r_1,r_2 \leq 10^{15}$