#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;
	}
};

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgcGFpcjxsbCwgbGw+IGxsMjsKCmNsYXNzIEJ1aWxkaW5nVG93ZXJzIHsKcHVibGljOgoJbGwgazsKCQoJbGwgZ2V0X21heChsbCBoMSwgbGwgaDIsIGxsIGRpc3QpewoJCWlmKGgyIDwgaDEpIHN3YXAoaDEsIGgyKTsKCQlsbCBsID0gaDEsIHIgPSBoMiArIGsqZGlzdDsKCQl3aGlsZShsIDwgcil7CgkJCWxsIG1pZCA9IGwgKyAoci1sKzEpLzI7CgkJCWJvb2wgb2sgPSAoKGFicyhoMS1taWQpK2stMSkvayArIChhYnMoaDItbWlkKStrLTEpL2sgPD0gZGlzdCk7IC8vIGNlaWwgdGhlIHJlc3VsdAoJCQlpZihvaykKCQkJCWwgPSBtaWQ7CgkJCWVsc2UKCQkJCXIgPSBtaWQtMTsKCQl9CgkKCQlyZXR1cm4gbWF4KGwsaDIpOwoJfQoJCglsb25nIGxvbmcgbWF4SGVpZ2h0KGludCBOLCBpbnQgSywgdmVjdG9yIDxpbnQ+IHgsIHZlY3RvciA8aW50PiB0KSB7CgkJdmVjdG9yPGxsMj4gYjsKCQlrID0gSzsKCQlpbnQgbSA9IChpbnQpeC5zaXplKCk7CgkJYi5wdXNoX2JhY2sobGwyKDEsMCkpOwoJCWZvcihpbnQgaSA9IDA7IGkgPCBtOyBpKyspewoJCQliLnB1c2hfYmFjayhsbDIoeFtpXSwgdFtpXSkpOwoJCX0KCQltKys7CgkJCgkJZm9yKGludCBpID0gMTsgaSA8IG07IGkrKyl7CgkJCWlmKGJbaS0xXS5zZWNvbmQgPCBiW2ldLnNlY29uZCkKCQkJCWJbaV0uc2Vjb25kID0gbWluKGJbaV0uc2Vjb25kLCBiW2ktMV0uc2Vjb25kICsgayooYltpXS5maXJzdC1iW2ktMV0uZmlyc3QpKTsKCQl9CgkJZm9yKGludCBpID0gbS0yOyBpID49IDA7IGktLSl7CgkJCWlmKGJbaSsxXS5zZWNvbmQgPCBiW2ldLnNlY29uZCkKCQkJCWJbaV0uc2Vjb25kID0gbWluKGJbaV0uc2Vjb25kLCBiW2krMV0uc2Vjb25kICsgayooYltpKzFdLmZpcnN0LWJbaV0uZmlyc3QpKTsKCQl9CgkJCgkJbGwgYW5zID0gMDsKCQlmb3IoaW50IGkgPSAxOyBpIDwgbTsgaSsrKQoJCQlhbnMgPSBtYXgoYW5zLCBnZXRfbWF4KGJbaV0uc2Vjb25kLCBiW2ktMV0uc2Vjb25kLCBiW2ldLmZpcnN0LWJbaS0xXS5maXJzdCkpOwoJCQkKCQlhbnMgPSBtYXgoYW5zLCAoKGxsKU4gLSBiW20tMV0uZmlyc3QpKmsgKyBiW20tMV0uc2Vjb25kKTsKCQlyZXR1cm4gYW5zOwoJfQp9Ow==