Problem: <!--

Problem D

-->

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.

<image> Fig. D-1 Tally Counters

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
>  a1 a2 ... an
>  b1 b2 ... bn
>

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, ai (1 ≤ ai ≤ m), separated by spaces. The third line contains the target values on counters, bi (1 ≤ bi ≤ 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






Example

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

4
0
14731

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define SIZE 2010

int N;
ll M;
ll dp[2][SIZE];
ll from[1005],to[1005];


void func(){

	for(int i = 0; i < N; i++){

		scanf("%lld",&from[i]);
	}

	for(int i = 0; i < N; i++){

		scanf("%lld",&to[i]);
		to[i] -= from[i];
		if(to[i] < 0){
			to[i] += M;
		}
	}

	int PRE = 0,CURRENT = 1;

	for(int i = 0; i < SIZE; i++){

		dp[PRE][i] = HUGE_NUM;
		dp[CURRENT][i] = HUGE_NUM;
	}

	for(ll k = 0; k <= 1000; k++){

		if(to[0]+M*k >= 0){

			dp[PRE][k] = to[0]+M*k;
		}
	}

	for(int i = 1; i < N; i++){
		for(ll k = 0; k < SIZE; k++){
			if(dp[PRE][k] == HUGE_NUM)continue;

			//下り:1つ左の加算値以下の、最も大きいiの加算値
			if(to[i-1] >= to[i]){

				dp[CURRENT][k] = min(dp[CURRENT][k],dp[PRE][k]); //下りなので押す回数は増えない

			}else{ //to[i-1] < to[i]

				if(k > 0){
					dp[CURRENT][k-1] = min(dp[CURRENT][k-1],dp[PRE][k]);
				}
			}

			//上り:1つ左の加算値より大きい、最も小さいiの加算値
			if(to[i-1] >= to[i]){

				dp[CURRENT][k+1] = min(dp[CURRENT][k+1],dp[PRE][k]+to[i]+M-to[i-1]); //増加分を足す

			}else{ //to[i-1] < to[i]

				dp[CURRENT][k] = min(dp[CURRENT][k],dp[PRE][k]+(to[i]-to[i-1]));
			}
		}
		swap(PRE,CURRENT);
		for(int k = 0; k < SIZE; k++){

			dp[CURRENT][k] = HUGE_NUM;
		}
	}

	ll ans = HUGE_NUM;

	for(int i = 0; i < SIZE; i++){

		ans = min(ans,dp[PRE][i]);
	}

	printf("%lld\n",ans);
}


int main(){

	while(true){

		scanf("%d %lld",&N,&M);
		if(N == 0 && M == 0)break;

		func();
	}

	return 0;
}