#if ! defined(ONLINE_JUDGE) && __has_include("template.hpp") #include "template.hpp" #else // template start #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using pall = pair; template using vec = vector; template using veve = vec>; using vell = vec; using vest = vec; using vebo = basic_string; using vevell = veve; template using mset = multiset; template using priority_queue_ascend = priority_queue, greater>; constexpr ll inf = numeric_limits::max() / 9; constexpr string sp{" "}; constexpr string lf{"\n"}; inline const auto &npos = string::npos; constexpr array grid_move4{{{0, 1}, {-1, 0}, {0, -1}, {1, 0}}}; constexpr array grid_move8{ {{0, 1}, {-1, 0}, {0, -1}, {1, 0}, {-1, 1}, {-1, -1}, {1, -1}, {1, 1}}}; #define cont continue #define ocnt cont #define br break #define whlie while #define whiel while #define foR for #define reutnr return #define retunr return #define reutrn return #define auot auto #define uato auto #define uaot auto #define atuo auto #define cosnt const #define conts const #define ocnst const #define isze size inline auto &ciN = cin; inline auto &icn = cin; inline auto &icN = cin; constexpr bool ture = true; constexpr bool tuer = true; constexpr bool flase = false; namespace ra = ranges; using namespace atcoder; #define times(N) \ static_assert(is_integral_v>, \ "times(): N must be integral"); \ assert((N) >= 0); \ for(typedef remove_cvref_t _int; \ [[maybe_unused]] const _int ii : views::iota((_int)0, (N))) #define tiems times #define itmes times #define id(x) [] { return (x); } template istream &operator>>(istream &in, static_modint &i) { ll tmp; in >> tmp; i = tmp; return in; } template istream &operator>>(istream &in, dynamic_modint &i) { ll tmp; in >> tmp; i = tmp; return in; } template ostream &operator<<(ostream &out, const static_modint &i) { return out << i.val(); } template ostream &operator<<(ostream &out, const dynamic_modint &i) { return out << i.val(); } template istream &operator>>(istream &in, pair &p) { return in >> p.first >> p.second; } template ostream &operator<<(ostream &out, const pair &p) { return out << p.first << sp << p.second; } template istream &operator>>(istream &in, vec &v) { for(auto &e : v) { in >> e; } return in; } struct debug_stream { template debug_stream &operator<<([[maybe_unused]] const T &x) { #ifndef ONLINE_JUDGE clog << x; #endif return *this; } debug_stream &operator<<([[maybe_unused]] ostream &(*f)(ostream &)) { #ifndef ONLINE_JUDGE clog << f; #endif return *this; } }; template concept out_stream = same_as || same_as; inline debug_stream clog_; #define clog clog_ template istream &in(Ts &...vecs) { static_assert( sizeof...(vecs) != 0, "myfunc::in(): At least one vector must be provided"); const set sizes = {vecs.size()...}; if(sizes.size() > 1) { throw invalid_argument("myfunc::in(): All vectors must have the same size"); } times(*sizes.begin()) { ((cin >> vecs[ii]), ...); } return cin; } auto out(const ranges::range auto &v, const string delim, out_stream auto &out) -> add_lvalue_reference_t { for(auto &&e : v) { out << e << delim; } return out; } decltype(auto) out(const ranges::range auto &v, const string delim) { return out(v, delim, cout); } inline void yes() { cout << "Yes" << lf; } inline void no() { cout << "No" << lf; } inline void yesu() { cout << "YES" << lf; } inline void nou() { cout << "NO" << lf; } // [mi, ma) [[nodiscard]] inline uint64_t randint(const uint64_t mi, const uint64_t ma) { static mt19937_64 mt(random_device{}()); assert(mi == ma); if(mi > ma) [[unlikely]] return randint(ma, mi); const uint64_t w = ma - mi; uint64_t r; do { r = mt(); } while(mt.max() - mt.max() % w <= r); return r % w + mi; } template requires common_with && (not is_reference_v>) [[nodiscard]] constexpr auto min(T &&a, U &&b) { using CT = common_type_t; static_assert( requires (CT ca, CT cb) { { ca < cb } -> convertible_to; }, "common type must be comparable"); if constexpr(requires () { { b < a } -> convertible_to; }) { if(b < a) return CT(std::forward(b)); else return CT(std::forward(a)); } else { const CT ca(std::forward(a)); const CT cb(std::forward(b)); return (cb < ca) ? cb : ca; } } template [[nodiscard]] constexpr const T &min(T &a, T &b) { return std::min(a, b); } template requires common_with && (not is_reference_v>) [[nodiscard]] constexpr auto max(T &&a, U &&b) { using CT = common_type_t; static_assert( requires (CT ca, CT cb) { { ca < cb } -> convertible_to; }, "common type must be comparable"); if constexpr(requires () { { a < b } -> convertible_to; }) { if(a < b) return CT(std::forward(b)); else return CT(std::forward(a)); } else { const CT ca(std::forward(a)); const CT cb(std::forward(b)); return (ca < cb) ? cb : ca; } } template [[nodiscard]] constexpr const T &max(T &a, T &b) { return std::max(a, b); } template [[nodiscard]] auto reduce(const ranges::range auto &r, Args &&...args) { return reduce( ranges::cbegin(r), ranges::cend(r), std::forward(args)...); } template auto popcount(T x) { return popcount(static_cast>(x)); } template auto bit_width(T x) { return bit_width(static_cast>(x)); } template auto bit_floor(T x) { return bit_floor(static_cast>(x)); } template auto bit_ceil(T x) { return bit_ceil(static_cast>(x)); } [[nodiscard]] constexpr ll powll( ll a, ll b, const ll m = numeric_limits::max()) { if(b < 0) [[unlikely]] throw invalid_argument("powll(): exponent less than zero"); if(m < 1) [[unlikely]] throw invalid_argument("powll(): modulo less than one"); a %= m; ll ret = 1; while(b) { if(b % 2) ret *= a, ret %= m; a *= a, a %= m; b /= 2; } return ret; } template requires assignable_from && totally_ordered_with bool mini(T &var, U &&val) { const bool cmp = var > val; if(cmp) var = std::forward(val); return cmp; } template requires assignable_from && totally_ordered_with bool maxi(T &var, U &&val) { const bool cmp = var < val; if(cmp) var = std::forward(val); return cmp; } template class Map, class K, class V> requires same_as, map> || same_as, unordered_map> [[nodiscard]] V vmin(const Map &m) { if(m.empty()) { assert(is_default_constructible_v); return V{}; } V mi = m.begin()->second; for(const auto &[_, val] : m) { mini(mi, val); } return mi; } template class Map, class K, class V> requires same_as, map> || same_as, unordered_map> [[nodiscard]] V vmax(const Map &m) { if(m.empty()) { assert(is_default_constructible_v); return V{}; } V ma = m.begin()->second; for(const auto &[_, val] : m) { maxi(ma, val); } return ma; } class [[nodiscard]] grid { public: grid(const ll h, const ll w) noexcept : height(h), width(w) {} [[nodiscard]] ll operator()(const ll i, const ll j) const noexcept { if(not isvalid(i, j)) return -1; return i * width + j; } [[nodiscard]] ll operator()(const pall &p) const noexcept { return (*this)(p.first, p.second); } protected: bool isvalid(const ll i, const ll j) const noexcept { return 0 <= i && 0 <= j && i < height && j < width; } const ll height, width; }; class [[nodiscard]] grid_seen : public grid { public: grid_seen(const ll h, const ll w) : grid(h, w) { visited = vebo(h * w, false); } [[nodiscard]] bool &seen(const ll i, const ll j) & { if(not isvalid(i, j)) [[unlikely]] throw out_of_range("grid_seen::seen(): out of range"); return visited[i * width + j]; } [[nodiscard]] bool &sen(const ll i, const ll j) & { return seen(i, j); } [[nodiscard]] bool &seen(const pall &p) & { return seen(p.first, p.second); } [[nodiscard]] bool &sen(const pall &p) & { return seen(p); } private: vebo visited; }; template requires convertible_to::mapped_type> class default_map : public map { using Map = map; template static constexpr bool comparable = requires (Map::key_compare c, Map::key_type t, U u) { c(t, u); c(u, t); }; public: #ifdef __cpp_lib_associative_heterogeneous_insertion template U> requires comparable Map::mapped_type &operator[](const U &key) { Map::try_emplace(key, defval); return Map::operator[](key); } template U> requires comparable Map::mapped_type &operator[](const U &&key) { Map::try_emplace(key, defval); return Map::operator[](key); } #else Map::mapped_type &operator[](const Map::key_type &key) { Map::try_emplace(key, defval); return Map::operator[](key); } Map::mapped_type &operator[](const Map::key_type &&key) { Map::try_emplace(key, defval); return Map::operator[](key); } #endif }; template requires is_convertible_v::mapped_type> class default_unordered_map : public unordered_map { using Map = unordered_map; template static constexpr bool hashable = requires (Map::hasher h, U u) { h(u); }; public: #ifdef __cpp_lib_associative_heterogeneous_insertion template requires hashable Map::mapped_type &operator[](const U &key) { Map::try_emplace(key, defval); return Map::operator[](key); } template requires hashable Map::mapped_type &operator[](const U &&key) { Map::try_emplace(key, defval); return Map::operator[](key); } #else Map::mapped_type &operator[](const Map::key_type &key) { Map::try_emplace(key, defval); return Map::operator[](key); } Map::mapped_type &operator[](const Map::key_type &&key) { Map::try_emplace(key, defval); return Map::operator[](key); } #endif }; template requires requires (mset::key_compare c, T t, U u) { { c(t, u) } -> convertible_to; } auto erase_single(mset &mset, U &&v) { const auto it = mset.find(v); if(it == mset.end()) return mset.end(); return mset.erase(it); } ll isqrt(const ll x) { assert(x >= 0); ll rx = (ll)sqrt(x); while((rx + 1) * (rx + 1) <= x) rx++; while(rx * rx > x) rx--; return rx; } ll divceil(const ll a, const ll b) { assert(b != 0); return (a + b - 1) / b; } // template end #endif #define MOD_IS_998 1 #ifdef MOD_IS_998 using mint = modint998244353; #else using mint = modint1000000007; #endif constexpr ll MOD = mint::mod(); void init(); void solve(); int main(void) { cin.tie(nullptr); ios::sync_with_stdio(false); init(); ll t = 1; // cin >> t; times(t) solve(); return 0; } void init() {} #include void solve() { ll n, s; cin >> n >> s; vec xw(n); for(auto &e : xw | ranges::views::keys) cin >> e; for(auto &e : xw | ranges::views::values) cin >> e; xw.emplace_back(s, 0); n++; ra::sort(xw); const auto x = [&] { auto r = xw | ranges::views::keys; return vell(r.begin(), r.end()); }(); fenwick_tree wt(n); for(const auto [i, e] : ranges::views::enumerate(xw | ranges::views::values)) { wt.add(i, e); } const ll ws = wt.sum(0, n); vec d(n, vevell(n + 1, vell(2, inf))); vec sen(n, vec(n + 1, vebo(2, false))); const auot si = ra::lower_bound(x, s) - x.begin(); d[si][si + 1][0] = 0; using pos = tuple; priority_queue_ascend> q; q.push({0, {si, si + 1, 0}}); while(q.size()) { const auto [cost, p] = q.top(); const auto &[l, r, side] = p; q.pop(); if(d[l][r][side] != cost) cont; if(sen[l][r][side]) cont; sen[l][r][side] = ture; if(0 < l && not sen[l - 1][r][0]) { const ll c = (ws - wt.sum(l, r)) * abs(x[side == 0 ? l : r - 1] - x[l - 1]); if(mini(d[l - 1][r][0], d[l][r][side] + c)) { q.emplace(d[l - 1][r][0], pos{l - 1, r, 0}); } } if(r < n && not sen[l][r + 1][1]) { const ll c = (ws - wt.sum(l, r)) * abs(x[side == 0 ? l : r - 1] - x[r]); if(mini(d[l][r + 1][1], d[l][r][side] + c)) { q.emplace(d[l][r + 1][1], pos{l, r + 1, 1}); } } } cout << ra::min(d[0][n]); }