题目描述

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

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

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

格式

输入格式：

第 $1$ 行读入 $1$ 个整数 $n$，代表天上的星星个数；

第 $2$ 行读入 $n$ 个整数 $a_i$ ， 代表第 $i$ 个星星的闪烁周期；

第 $3$ 行读入 $n$ 个整数 $b_i$​ ， 代表第 $i$ 个星星的开始闪烁时间；

第 $4$ 行读入 $3$ 个整数 $l,r,c$，代表开始计数时间，结束时间，计数睡着的次数。

数据保证 $1≤n≤10^5 ，1≤a_i ,b_i​ ,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。