#include #include #define rep(i,n) for(int i=0;i vi; typedef vector vl; typedef vector> vvi; typedef vector> vvl; typedef long double ld; typedef pair P; ostream& operator<<(ostream& os, const modint& a) {os << a.val(); return os;} template ostream& operator<<(ostream& os, const static_modint& a) {os << a.val(); return os;} template ostream& operator<<(ostream& os, const dynamic_modint& a) {os << a.val(); return os;} template istream& operator>>(istream& is, vector& v){int n = v.size(); assert(n > 0); rep(i, n) is >> v[i]; return is;} template ostream& operator<<(ostream& os, const pair& p){os << p.first << ' ' << p.second; return os;} template ostream& operator<<(ostream& os, const vector& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : " "); return os;} template ostream& operator<<(ostream& os, const vector>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : ""); return os;} template ostream& operator<<(ostream& os, const set& se){for(T x : se) os << x << " "; os << "\n"; return os;} template ostream& operator<<(ostream& os, const unordered_set& se){for(T x : se) os << x << " "; os << "\n"; return os;} template ostream& operator<<(ostream& os, const atcoder::segtree& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;} template ostream& operator<<(ostream& os, const atcoder::lazy_segtree& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;} template void chmin(T& a, T b){a = min(a, b);} template void chmax(T& a, T b){a = max(a, b);} // Coodinate Compression // https://youtu.be/fR3W5IcBGLQ?t=8550 template struct CC { bool initialized; vector xs; CC(): initialized(false) {} void add(T x) { xs.push_back(x);} void init() { sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(),xs.end()),xs.end()); initialized = true; } int operator()(T x) { if (!initialized) init(); return upper_bound(xs.begin(), xs.end(), x) - xs.begin() - 1; } T operator[](int i) { if (!initialized) init(); return xs[i]; } int size() { if (!initialized) init(); return xs.size(); } }; const long long INF = 1001001001001001; using S = long long; S op(S a, S b){ return max(a, b); } S e(){ return -INF; } int main(){ int n; long long k; cin >> n >> k; vector t(n); vector x(n); vector c(n); cin >> t >> x >> c; t.push_back(0); x.push_back(0); c.push_back(0); vector ktpx; vector ktmx; rep(i, n + 1) ktpx.push_back(k * t[i] + x[i]); rep(i, n + 1) ktmx.push_back(k * t[i] - x[i]); CC cc; rep(i, n + 1) cc.add(ktmx[i]); int m = cc.size(); segtree seg(m); map> event; rep(i, n + 1) event[ktpx[i]].push_back(i); bool init = false; for(auto& [z, vec] : event){ sort(vec.begin(), vec.end(), [&](int i, int j){return ktmx[i] < ktmx[j];}); for(int i : vec){ if(i == n){ seg.set(cc(0), 0); }else{ int idx = cc(ktmx[i]); auto val = seg.prod(0, idx + 1); if(val != -INF) seg.set(idx, val + c[i]); } } // cout << seg; } long long ans = seg.all_prod(); cout << ans << "\n"; return 0; }