题目描述

UCPC 的出题人们终于订到了传说中的“万物回转寿司店”。这家店不只寿司在转，厨师和顾客也会一起转。

共有 $n$ 名出题人排成一排就座，同时厨房安排了 $n+1$ 名厨师。第 $i$ 名厨师每分钟可以制作 $b_i$ 片寿司。

刚开始时，服务员已经给第 $i$ 个位置上的出题人发了 $a_i$ 片寿司。

之后，每一分钟按如下顺序发生三件事：

1. 对所有 $1\le i\le n$，当前在第 $i$ 个位置的厨师给当前在第 $i$ 个位置的出题人制作寿司，数量等于该厨师一分钟能做的寿司片数。当前在第 $n+1$ 个位置的厨师休息，不制作寿司。
2. 厨师整体轮转一次：原来在第 $1$ 个位置的厨师到第 $2$ 个位置，原来在第 $2$ 个位置的厨师到第 $3$ 个位置，依此类推，原来在第 $n+1$ 个位置的厨师到第 $1$ 个位置。
3. 出题人整体轮转一次：原来在第 $1$ 个位置的出题人到第 $2$ 个位置，原来在第 $2$ 个位置的出题人到第 $3$ 个位置，依此类推，原来在第 $n$ 个位置的出题人到第 $1$ 个位置。

每名出题人只要手上凑够一组寿司，就会立刻吃掉这一组。这里一组寿司恰好包含 $k$ 片，寿司种类不重要；这些寿司可以来自初始发放，也可以来自一个或多个厨师。吃寿司所需时间忽略不计。

出题人们不喜欢剩饭，所以他们希望最终每个人手上都剩下 $0$ 片寿司。请问从开始后经过多少分钟，他们才能全部吃完？

如果无论等待多久都无法让所有人手上的寿司数同时变成 $0$，输出 $-1$。

输入格式

第一行包含两个整数 $n,k$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每名出题人初始拥有的寿司片数。

第三行包含 $n+1$ 个整数 $b_1,b_2,\ldots,b_{n+1}$，表示每名厨师每分钟制作的寿司片数。

输出格式

输出一行一个整数，表示所有出题人手上的寿司数量都变成 $0$ 所需的最少分钟数。

如果永远无法达成，输出 $-1$。

数据范围

• $1\le n\le 2000$；
• $2\le k\le 10^6$；
• $0\le a_i<k$；
• $1\le b_i<k$。

样例 1

输入

3 3
0 0 1
2 1 1 2

输出

3

样例1图示

展示每一分钟后厨师、出题人和寿司数量的对应关系。

样例 2

输入

3 3
0 0 0
2 1 1 2

输出

0

解释

样例 2 中，所有出题人在开始时手上的寿司数已经都是 $0$，因此答案为 $0$。