You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

平头哥跋山涉水来到户外，准备拍摄天上的星星。但是星星一闪一闪的

题目描述

今天晚上，天上一共有 n 颗星星在闪烁，不同的星星会从第 $a_i$ 秒开始闪；（在 $a_i$ 会闪一次），然后每 $b_i$ 秒就会再闪一次，平头哥今天晚上准备总共拍下 x 颗星星。 星星每闪一次平头哥便按一次快门，（不用在意平头哥的快门速度能不能捕捉到。） 然后同时记作拍下一颗星星。若天上同时有m颗星星在闪，则记作m颗。

假设平头哥今晚上从p秒开始拍摄，q秒时天亮了，星星消失。请你帮一帮平头哥算一下今晚上能不能拍到x颗星星。

输入格式

第一行输入 1 个数 n，表示天上星星的总数； 第二行输入 n 个整数 $a_i$ ，表示第i个星星的开始闪烁时间； 第三行读入 n 个整数 $b_i$ ，表示第i个星星的闪烁周期； 第四行读入三个整数p，q，x代表开始时间，结束时间，目标数量。

数据说明：

$1<= n <= 10^5$ 其他数据不超过$10^{18}$

输出格式

如果能完成目标输出当前时间。

如果不能完成就输出 -1。 样例输入

3
1 3 5
3 5 9
1 30 20

样例输出

16

Limitation

0.5s, 1024KiB for each test case.