#include using namespace std; //* ATCODER #include using namespace atcoder; typedef modint998244353 mint; //*/ /* BOOST MULTIPRECISION #include using namespace boost::multiprecision; //*/ typedef long long ll; #define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++) #define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--) template bool chmin(T &a, const T &b) { if (a <= b) return false; a = b; return true; } template bool chmax(T &a, const T &b) { if (a >= b) return false; a = b; return true; } template T max(vector &a){ assert(!a.empty()); T ret = a[0]; for (int i=0; i<(int)a.size(); i++) chmax(ret, a[i]); return ret; } template T min(vector &a){ assert(!a.empty()); T ret = a[0]; for (int i=0; i<(int)a.size(); i++) chmin(ret, a[i]); return ret; } template T sum(vector &a){ T ret = 0; for (int i=0; i<(int)a.size(); i++) ret += a[i]; return ret; } #include template struct range_tree { typedef std::pair Point; public: range_tree() {} void add_point(IntType a, IntType b) { points.emplace_back(Point{a, b}); } std::vector merge_points(std::vector &a, std::vector &b) { std::vector ret((int)a.size() + (int)b.size()); int piv = 0; int piva = 0; int pivb = 0; while (piva < (int)a.size() || pivb < (int)b.size()) { if (piva == (int)a.size()) { ret[piv++] = b[pivb++]; }else if(pivb == (int)b.size()){ ret[piv++] = a[piva++]; }else{ if (a[piva].second <= b[pivb].second) { assert(a[piva].first < b[pivb].first); ret[piv++] = a[piva++]; }else{ ret[piv++] = b[pivb++]; } } } assert(piv == (int)a.size() + (int)b.size()); return ret; } void build() { std::sort(points.begin(), points.end()); points.erase(unique(points.begin(), points.end()), points.end()); if (points.empty()) return; IntType memo = points[0].first; xlist.emplace_back(memo); std::vector> tmp_idy(1, std::vector(1,points[0])); for (int i=1; i<(int)points.size(); i++){ if (points[i].first != memo) { assert(memo < points[i].first); tmp_idy.emplace_back(std::vector(1, points[i])); memo = points[i].first; xlist.emplace_back(memo); }else{ tmp_idy.back().emplace_back(points[i]); } } assert(tmp_idy.size() == xlist.size()); n = (int)xlist.size(); sz = 1; while (sz < n) { sz <<= 1; } idy.resize(2 * sz); seg.resize(2 * sz); for (int i=0; i<(int)xlist.size(); i++){ idy[i+sz] = tmp_idy[i]; seg[i+sz] = atcoder::segtree((int)idy[i+sz].size()); } for (int i=sz-1; i>=1; i--){ idy[i] = merge_points(idy[2*i], idy[2*i+1]); seg[i] = atcoder::segtree((int)idy[i].size()); } } int y_lower_bound(std::vector &a, IntType q) { int ub = (int)a.size() + 1; int lb = 0; while (ub - lb > 1) { int t = (ub + lb) / 2; if (q > a[t-1].second) { lb = t; }else{ ub = t; } } return lb; } int yx_lower_bound(std::vector &a, Point &p) { int ub = (int)a.size() + 1; int lb = 0; while (ub - lb > 1) { int t = (ub + lb) / 2; if (p.second > a[t-1].second || (p.second == a[t-1].second && p.first > a[t-1].first)) { lb = t; }else{ ub = t; } } return lb; } S get(IntType x, IntType y) { Point p = Point{x, y}; int i = lower_bound(points.begin(), points.end(), p) - points.begin(); if (i == (int)points.size()) return e(); if (points[i] != p) return e(); return seg[1].get(yx_lower_bound(idy[1], p)); } S prod_inner(int ind, IntType d, IntType u) { int di = y_lower_bound(idy[ind], d); int ui = y_lower_bound(idy[ind], u); return seg[ind].prod(di, ui); } S prod(IntType l, IntType r, IntType d, IntType u) { int li = lower_bound(xlist.begin(), xlist.end(), l) - xlist.begin(); int ri = lower_bound(xlist.begin(), xlist.end(), r) - xlist.begin(); li += sz; ri += sz; S retl = e(), retr = e(); while (li < ri) { if (li & 1) { retl = op(retl, prod_inner(li, d, u)); li++; } if (ri & 1){ ri--; retr = op(prod_inner(ri, d, u), retr); } li >>= 1; ri >>= 1; } return op(retl, retr); } void set(IntType x, IntType y, S val) { Point p = Point{x, y}; int i = lower_bound(points.begin(), points.end(), p) - points.begin(); assert (i < (int)points.size()); assert (points[i] == p); int xi = lower_bound(xlist.begin(), xlist.end(), p.first) - xlist.begin(); xi += sz; while (xi > 0) { seg[xi].set(yx_lower_bound(idy[xi], p), val); xi >>= 1; } } private: int n, sz; std::vector points; std::vector xlist; std::vector> idy; std::vector> seg; }; ll op(ll a, ll b){ return max(a, b); } ll e(){ return -1e18; } int main(){ int n; cin >> n; ll k; cin >> k; vector t(n), x(n), c(n); vector> f(n); rep(i,0,n) cin >> t[i]; rep(i,0,n) cin >> x[i]; rep(i,0,n) cin >> c[i]; rep(i,0,n) f[i] = make_tuple(t[i], x[i], c[i]); sort(f.begin(), f.end()); rep(i,0,n){ t[i] = get<0>(f[i]); x[i] = get<1>(f[i]); c[i] = get<2>(f[i]); } range_tree wm; rep(i,0,n){ wm.add_point(x[i]+k*t[i], x[i]-k*t[i]); } wm.add_point(0, 0); wm.build(); wm.set(0, 0, 0); rep(i,0,n){ ll X = x[i]+k*t[i]; ll Y = x[i]-k*t[i]; ll Z = wm.prod(-9e18, X+1, Y, 9e18) + c[i]; wm.set(X, Y, Z); } cout << wm.prod(-9e18, 9e18, -9e18, 9e18) << '\n'; }