Revolving Sushi

The UCPC city has the most famous conveyor belt sushi restaurant in the world. Its name is "the restaurant where everything revolves"! The restaurant became popular on social media for its unusual concept: the cooks and the guests all revolve. The UCPC problem setters booked a table months ago, and today they finally visited.

A total of $N$ problem setters visited the restaurant, so the kitchen prepared $N+1$ cooks to match. The $i$-th cook can make $b_i$ pieces of sushi per minute. At the start, the waiter seated the problem setters in a row and gave $a_i$ pieces of sushi to the $i$-th setter. Then the following actions repeated in order every minute.

1. For every $i$ with $1\leq i\leq N$, the cook at position $i$ makes sushi for the setter at position $i$. The amount made equals the number of pieces that cook can make per minute. The cook at position $N+1$ makes no sushi and rests.
2. The cooks rotate once. That is, the cook originally at position 1 moves to position 2, the cook originally at position 2 moves to position 3, ..., and the cook originally at position $N+1$ moves to position 1.
3. The setters rotate once. That is, the setter originally at position 1 moves to position 2, the setter originally at position 2 moves to position 3, ..., and the setter originally at position $N$ moves to position 1.

Each setter eats one set of sushi as soon as they have one set gathered. A set is a bundle of $K$ pieces, regardless of type. Time spent eating is ignored.

The setters hate wasting food, so they want to keep eating until everyone has 0 pieces left. How many minutes after the meal starts will the meal end?

The first line contains integers $N$ and $K$, separated by a space. ($1\leq N\leq 2\,000$, $2\leq K\leq 1\,000\,000$)

The second line contains $a_1, a_2, \cdots, a_N$, separated by spaces. ($0\leq a_i\leq K-1$)

The third line contains $b_1, b_2, \cdots, b_{N+1}$, separated by spaces. ($1\leq b_i\leq K-1$)

Print the number of minutes it takes the setters to finish the meal. If the setters never finish the meal, even after infinite time, print -1 instead.