该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

红绿灯

题目描述

奶龙每天上学都会经过一条 $n$ 个红绿灯的道路， 奶龙在时刻 $0$ 醒来，它打算在休息一会后出发。

对于第 $i$ 个红路灯，会按照一个周期重复进行工作，从 $0$ 时刻作为一个周期的开始，具体地，每个周期里，这个灯会绿 $g_i$ 秒，红 $r_i$ 秒，也就是说，这个灯会在时刻 $(0,g_i]$ 保持绿色，时刻 $(g_i,g_i+r_i]$ 保持红色，时刻 $(g_i+r_i,2g_i+r_i]$ 保持绿色以此类推。

奶龙从一个红绿灯走到下一个红绿灯需要 $1$ 单位时间，从家到第一个红绿灯也需要 $1$ 单位时间，通过第 $n$ 个红绿灯时立刻到达学校。

奶龙被要求最晚到达学校的时间是 $m$ ，也就是说它到达学校的时刻不能超过 $m$，否则会迟到，数据保证奶龙从 $0$ 时刻出发不可能迟到，请求出奶龙最晚的出发时间。

注意，时刻的流动都是整数，也就是说奶龙不能在非整数时刻通过一个路口，奶龙通过路口时间不记。

求保证奶龙不迟到的最晚出发时刻。

输入格式

第一行两个整数 $n,m$ ，表示红绿灯数量和上学要求的时间。

第二行包含 $n$ 个整数 $g_1,g_2,...,g_n$ 表示每个红绿灯的绿灯时间。

第三行包含 $n$ 个整数 $r_1,r_2,...,r_n$ 表示每个红绿灯的红灯时间。

输出格式

输出一个整数表示奶龙最晚的出发时刻。

样例 #1

样例输入 #1

2 5
2 3
1 2

样例输出 #1

1

样例 #2

样例输入 #2

4 25
6 2 3 4 
7 9 7 2

样例输出 #2

5

样例 #3

样例输入 #3

20 90
6 3 8 2 9 3 4 5 1 8 10 4 2 6 5 3 2 7 9 9 
1 10 9 6 3 5 9 10 2 5 2 8 1 1 6 9 3 7 5 8

样例输出 #3

39

提示

对于第一个样例：

奶龙如果在 $1$ 时刻出发，在 $2$ 时刻到达第一个灯，此时是绿灯直接通过，在 $3$ 时刻到达第二个灯，此时是绿灯直接通过，在时刻 $3$ 提前到达学校。

奶龙如果在 $2$ 时刻出发，在 $3$ 时刻到达第一个灯，此时是红灯，等待到时刻 $4$ 时灯变绿通过，在 $5$ 时刻到达第二个灯，此时是红灯，等待到时刻 $6$ 时灯变绿通过，在时刻 $6$ 到达学校，迟到了。

对于 $20 \%$ 的数据 $n,g_i,r_i \le 10，m \le 1000$ 。

对于另外 $30 \%$ 的数据 $n,g_i,r_i \le 100，m \le 10^9$ 。

对于 $100 \%$ 的数据 $n \le 10^6,g_i,r_i \le 10^9,m \le 10^{18}$ 。

本题输入量较大, 请注意读入对性能造成的影响.