天上有 n 颗星星，每颗星星自第 bi​ 秒开始（包含第 bi​ 秒），每 ai​ 秒便会闪烁一次，小度 今晚有一点失眠，所以他想来数星星，天上的星星每闪烁一次，小度便会在心中记一次数，如果同时有 x 颗星星在闪烁，小度也会计数 x 次。

假设小度今晚会从第 l 秒开始数，第 r 秒天便亮了，但是在计数到 c 次及以上的时候，小度便会睡着。

请问你能帮小度预估，今晚是否能睡着吗？如果能，将会在多少秒时睡着。

格式

输入格式：

第 1 行读入 1 个整数 n，代表天上的星星个数；
第 2 行读入 n 个整数 ai​， 代表第 𝑖i 个星星的闪烁周期；
第 3 行读入 n 个整数 bi​， 代表第 𝑖i 个星星的开始闪烁时间；
第 4 行读入 3 个整数 l,r,c，代表开始计数时间，结束时间，计数睡着的次数。
数据保证 1≤n≤10^5，1≤ai​,bi​,l,r,c≤10^18，l≤r。

输出格式：

如果小度能够睡着，那么输出小度睡着的时候，否则输出 -1。

样例 1

输入：

2 1 2 1 1 1 10 4 

输出：

3 

样例 2

输入：

1 1 1 30 40 12

复制

输出：

-1

复制

样例 3

输入：

3 1 3 5 3 5 9 1 30 20 

输出：

16 

样例 4

输入：

1 2 3 1 1000000000000000000 499999999999999999 

输出：

999999999999999999

复制

备注

样例1解释：
第 1 秒，星星 1 与 星星 2 闪烁一次；
第 2 秒，星星 1 闪烁一次；
第 3 秒，星星 1 与 星星 2 闪烁一次；
在第 3 秒时，所有星星共 5 次，大于等于 4 次，所以小度会在第 3 秒睡着。
所以答案为 3。
样例2解释：
第 30 秒至第 40 秒期间，星星共闪烁 11 次，没有满足小度会睡着的条件，输出 -1。 

思路：二分求解，对每一个时间t，确定到t可以观察到多少个星星闪耀。（题目不难，就是可能有细节错，建议先打个草稿分一下情况）（ps:这星耀难度像签到，hh）

三种情况：

1：第i个星星开始时间大于t，直接跳过。

2：开始时间在l和t之间，计算t到b[i]的闪耀次数。

3：开始时间t小于l，计算l-1到b[i]和t到b[i]的闪耀次数，然后相减。（博主一开始一直是l到b[i]，一直错，/(ㄒoㄒ)/~~）

代码;

#include using namespace std; #define int long long const int N=1e5+10; int a[N]; int b[N]; int l,r,c,n; int l1,r1; int check(int x){ 	int count=0; 	for(int i=1;i<=n;i++) 	if(b[i]>x)continue; 	else if(b[i]<=x&&b[i]>=l){ 		count=count+(x-b[i])/a[i]+1; 		if(count>=c)return 1; 	} 	else {         count=count+(x-b[i])/a[i]-(l-1-b[i])/a[i];         if(count>=c)return 1;     } 	return 0; } signed main(){ 	scanf("%lld",&n); 	for(int i=1;i<=n;i++) 	scanf("%lld",&a[i]); 	for(int i=1;i<=n;i++) 	scanf("%lld",&b[i]); 	 	scanf("%lld%lld%lld",&l,&r,&c); 	 	l1=l; 	r1=r; 	 	while(l1