题目描述

有 $N$ 名出题人来到一家“什么都会旋转”的回转寿司店，店里安排了 $N+1$ 名厨师。

第 $i$ 名厨师每分钟能制作 $b_i$ 个寿司。初始时，服务员让 $N$ 名出题人按顺序坐下，并给第 $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}$，表示各厨师每分钟制作的寿司数。

输出格式

输出所有出题人结束用餐所需的最少分钟数。

若永远无法结束，输出 -1。

样例 1

输入

3 3
0 0 1
2 1 1 2

输出

3

样例 1 中各时刻的状态如下。

样例 2

输入

3 3
0 0 0
2 1 1 2

输出

0