在 UCPC，有一家世界闻名的回转寿司店，店名叫“什么都转回转寿司店”！这家回转寿司店因其厨师和顾客都会旋转的独特概念而在社交媒体上获得了极高的人气。UCPC 的出题人们不想错过这家名店，于是提前几个月预订了座位，今天他们终于光顾了这家回转寿司店！

共有 $n$ 位出题人光顾了这家回转寿司店，厨房里相应地有 $n+1$ 位厨师待命。第 $i$ 位厨师每分钟可以制作 $b_i$ 个寿司。起初，服务员将出题人排成一排，并给第 $i$ 个位置的出题人分发了 $a_i$ 个寿司。随后，每分钟按顺序重复执行以下动作：

• 对于所有 $1 \le i \le n$，位于第 $i$ 个位置的厨师为位于第 $i$ 个位置的出题人制作寿司。制作的寿司数量等于该厨师每分钟能制作的数量。位于第 $n+1$ 个位置的厨师不制作寿司，而是休息。
• 厨师旋转一次。即，原本在第 1 个位置的厨师移动到第 2 个位置，原本在第 2 个位置的厨师移动到第 3 个位置，以此类推，原本在第 $n+1$ 个位置的厨师移动到第 1 个位置。
• 出题人旋转一次。即，原本在第 1 个位置的出题人移动到第 2 个位置，原本在第 2 个位置的出题人移动到第 3 个位置，以此类推，原本在第 $n$ 个位置的出题人移动到第 1 个位置。

每位出题人一旦拥有了足够的寿司，就会立即吃掉一套。这里，一套寿司是指恰好 $k$ 个寿司的组合，无论种类如何（有些可能由服务员提供，有些由一位或多位厨师制作）。吃寿司所花费的时间忽略不计。

出题人们不喜欢浪费食物，因此他们会一直吃，直到所有人的寿司都剩下 0 个为止。请问他们吃完这顿饭需要多少分钟？

输入格式

第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 2000$; $2 \le k \le 10^6$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le k-1$)。 第三行包含 $n+1$ 个整数 $b_1, b_2, \dots, b_{n+1}$ ($1 \le b_i \le k-1$)。

输出格式

输出出题人吃完饭所需的分钟数。如果即使经过无限长的时间他们也无法吃完，则输出 $-1$。

样例

样例输入 1

3 3
0 0 1
2 1 1 2

样例输出 1

3

样例输入 2

3 3
0 0 0
2 1 1 2

样例输出 2

0

说明

在第一个样例中，可视化出题人和厨师的位置，以及每位出题人收到的寿司数量和每位厨师在每个时间间隔内能制作的寿司数量，如下所示：

在第二个样例中，出题人在开始吃之前就已经吃完了（即不需要额外时间）。