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>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os, const map<T,U>& mp){ os << "{"; for(auto& p : mp){ os << p << ","; } os << "}"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
template<typename T> ostream& operator<<(ostream& os,const set<T>& st){ os<<"{"; for(T v:st) os<<v<<","; os <<"}"; return os; }
template<typename T,typename U> inline void chmax(T &x,U y){ if(y>x) x = y; }
template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }
using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int,int>;
using vi = std::vector<int>;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
//constexpr double eps = 1e-14; 
constexpr double eps = 1e-10; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

void solve(ll n,ll m){
    vector<ll> a(n),b(n);
    rep(i,n){cin >> a[i];a[i]--;}
    rep(i,n){cin >> b[i],b[i]--;}
    vector<ll> c(n);
    rep(i,n) c[i] = (b[i]-a[i]+m)%m;

    //cout << c << endl;

    // dp[i][j] := i番目までを見たときにi番目がc[i]+jm回操作しているときの最小回数
    vector<vector<ll>> dp(n+5,vector<ll>(n+5,n*m+10));
    for(int i=0;i<=n;i++){
        dp[0][i] = c[0] + i * m;
    }

    for(int i=1;i<n;i++){
        for(int j=0;j<=n;j++){
            for(int k=max<ll>(0,j-3);k<=min<ll>(n,j+3);k++){
                dp[i][j] = min(dp[i][j], dp[i-1][k] + max(0ll,(c[i]+j*m) - (c[i-1]+k*m)));
            }
        }
    }

    ll ans = LINF;
    for(int i=0;i<=n;i++){
        ans = min(ans, dp[n-1][i]);
    }
    cout << ans << endl;

    /* for(int i=0;i<=n;i++){ */
    /*     for(int j=0;j<=m;j++){ */
    /*         cout << dp[i][j] << "\t"; */
    /*     } */
    /*     cout << endl; */
    /* } */
}

int main(){
    while(true){
        int n,m; cin >> n >> m;
        if(n==0 and m==0) break;
        solve(n,m);
    }
}