#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; } //https://hitonanode.github.io/cplib-cpp/segmenttree/rangetree.hpp.html #include #include #include #include // CUT begin // 逆元を要求しない領域木 template class rangetree { int n; using Pt = std::pair; std::vector _pts; std::vector> _range2yxs; std::vector> segtrees; void _set(int v, Pt p, S val) { auto i = std::distance( _range2yxs[v].begin(), std::lower_bound(_range2yxs[v].begin(), _range2yxs[v].end(), Pt{p.second, p.first})); segtrees[v].set(i, val); } void _add(int v, Pt p, S val) { auto i = std::distance( _range2yxs[v].begin(), std::lower_bound(_range2yxs[v].begin(), _range2yxs[v].end(), Pt{p.second, p.first})); segtrees[v].set(i, op(segtrees[v].get(i), val)); } S _prod(int v, Coordinate yl, Coordinate yr) const { auto comp = [&](const Pt &l, const Pt &r) { return l.first < r.first; }; auto il = std::distance( _range2yxs[v].begin(), std::lower_bound(_range2yxs[v].begin(), _range2yxs[v].end(), Pt{yl, yl}, comp)); auto ir = std::distance( _range2yxs[v].begin(), std::lower_bound(_range2yxs[v].begin(), _range2yxs[v].end(), Pt{yr, yr}, comp)); return segtrees[v].prod(il, ir); } public: rangetree() = default; void add_point(Coordinate x, Coordinate y) noexcept { _pts.emplace_back(x, y); } void build() { std::sort(_pts.begin(), _pts.end()); _pts.erase(std::unique(_pts.begin(), _pts.end()), _pts.end()); n = _pts.size(); _range2yxs.resize(n * 2); for (int i = 0; i < n; i++) _range2yxs[n + i] = {{_pts[i].second, _pts[i].first}}; for (int i = n - 1; i > 0; i--) { auto &lch = _range2yxs[i * 2]; auto &rch = _range2yxs[i * 2 + 1]; std::merge( lch.begin(), lch.end(), rch.begin(), rch.end(), std::back_inserter(_range2yxs[i])); _range2yxs[i].erase( std::unique(_range2yxs[i].begin(), _range2yxs[i].end()), _range2yxs[i].end()); } for (const auto &v : _range2yxs) segtrees.emplace_back(v.size()); } void set(Coordinate x, Coordinate y, S val) { int i = std::distance(_pts.begin(), std::lower_bound(_pts.begin(), _pts.end(), Pt{x, y})); assert(i < n and _pts[i] == std::make_pair(x, y)); for (i += n; i; i >>= 1) _set(i, {x, y}, val); } void add(Coordinate x, Coordinate y, S val) { int i = std::distance(_pts.begin(), std::lower_bound(_pts.begin(), _pts.end(), Pt{x, y})); assert(i < n and _pts[i] == std::make_pair(x, y)); for (i += n; i; i >>= 1) _add(i, {x, y}, val); } S prod(Coordinate xl, Coordinate xr, Coordinate yl, Coordinate yr) const { auto comp = [](const Pt &l, const Pt &r) { return l.first < r.first; }; int l = n + std::distance(_pts.begin(), std::lower_bound(_pts.begin(), _pts.end(), Pt{xl, yr}, comp)); int r = n + std::distance(_pts.begin(), std::lower_bound(_pts.begin(), _pts.end(), Pt{xr, yr}, comp)); S ret = e(); while (l < r) { if (l & 1) ret = op(ret, _prod(l++, yl, yr)); if (r & 1) ret = op(ret, _prod(--r, yl, yr)); l >>= 1, r >>= 1; } return ret; } S get(Coordinate x, Coordinate y) const { return prod(x, x + 1, y, y + 1); } }; 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]); } rangetree 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'; }