#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> ll2;

class BuildingTowers {
public:
	ll k;
	
	ll get_max(ll h1, ll h2, ll dist){
		if(h2 < h1) swap(h1, h2);
		ll l = h1, r = h2 + k*dist;
		while(l < r){
			ll mid = l + (r-l+1)/2;
			bool ok = ((abs(h1-mid)+k-1)/k + (abs(h2-mid)+k-1)/k <= dist); // ceil the result
			if(ok)
				l = mid;
			else
				r = mid-1;
		}
	
		return max(l,h2);
	}
	
	long long maxHeight(int N, int K, vector <int> x, vector <int> t) {
		vector<ll2> b;
		k = K;
		int m = (int)x.size();
		b.push_back(ll2(1,0));
		for(int i = 0; i < m; i++){
			b.push_back(ll2(x[i], t[i]));
		}
		m++;
		
		for(int i = 1; i < m; i++){
			if(b[i-1].second < b[i].second)
				b[i].second = min(b[i].second, b[i-1].second + k*(b[i].first-b[i-1].first));
		}
		for(int i = m-2; i >= 0; i--){
			if(b[i+1].second < b[i].second)
				b[i].second = min(b[i].second, b[i+1].second + k*(b[i+1].first-b[i].first));
		}
		
		ll ans = 0;
		for(int i = 1; i < m; i++)
			ans = max(ans, get_max(b[i].second, b[i-1].second, b[i].first-b[i-1].first));
			
		ans = max(ans, ((ll)N - b[m-1].first)*k + b[m-1].second);
		return ans;
	}
};