Tally Counters

A number of tally counters are placed in a row. Pushing the button on a counter will increment the displayed value by one, or, when the value is already the maximum, it goes down to one. All the counters are of the same model with the same maximum value.

Starting from the values initially displayed on each of the counters, you want to change all the displayed values to target values specified for each. As you don't want the hassle, however, of pushing buttons of many counters one be one, you devised a special tool. Using the tool, you can push buttons of one or more adjacent counters, one push for each, in a single operation. You can choose an arbitrary number of counters at any position in each operation, as far as they are consecutively lined up.

How many operations are required at least to change the displayed values on counters to the target values?

Input

The input consists of multiple datasets, each in the following format.

n m
a₁ a₂ ... a_n
b₁ b₂ ... b_n

Each dataset consists of 3 lines. The first line contains n (1 ≤ n ≤ 1000) and m (1 ≤ m ≤ 10000), the number of counters and the maximum value displayed on counters, respectively. The second line contains the initial values on counters, a_i (1 ≤ a_i ≤ m), separated by spaces. The third line contains the target values on counters, b_i (1 ≤ b_i ≤ m), separated by spaces.

The end of the input is indicated by a line containing two zeros. The number of datasets does not exceed 100.

Output

For each dataset, print in a line the minimum number of operations required to make all of the counters display the target values.

Sample Input

4 5
2 3 1 4
2 5 5 2
3 100
1 10 100
1 10 100
5 10000
4971 7482 1238 8523 1823
3287 9013 9812 297 1809
0 0

Output for the Sample Input

4
0
14731

---