题目背景

这是 $CSP-J$ 模拟赛的 $T1$ 。

题目描述

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

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

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

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

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

输入格式

输入三行。

第一行两个整数 $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

提示

样例解释】：

对于第一个样例：

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

$Alice$ 如果在 $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}$