#line 1 "..\\Main.cpp" #include #line 2 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\misc\\nyaanio.hpp" #include #include #include #include #include #include namespace fastio { static constexpr int SZ = 1 << 17; char inbuf[SZ], outbuf[SZ]; int in_left = 0, in_right = 0, out_right = 0; struct Pre { char num[40000]; constexpr Pre() : num() { for (int i = 0; i < 10000; i++) { int n = i; for (int j = 3; j >= 0; j--) { num[i * 4 + j] = n % 10 + '0'; n /= 10; } } } } constexpr pre; inline void load() { int len = in_right - in_left; memmove(inbuf, inbuf + in_left, len); in_right = len + fread(inbuf + len, 1, SZ - len, stdin); in_left = 0; if(in_right != SZ) inbuf[in_right] = '\000'; } inline void flush() { fwrite(outbuf, 1, out_right, stdout); out_right = 0; } inline void skip_space() { if (in_left + 32 > in_right) load(); while (inbuf[in_left] <= ' ') in_left++; } inline void rd(char& c) { if (in_left + 32 > in_right) load(); c = inbuf[in_left++]; } template inline void rd(T& x) { if (in_left + (int)sizeof(T) * 8 > in_right) load(); char c; do c = inbuf[in_left++]; while (c < '-'); [[maybe_unused]] bool minus = false; if constexpr (std::is_signed::value == true) { if (c == '-') minus = true, c = inbuf[in_left++]; } x = 0; while (c >= '0') { x = x * 10 + (c & 15); c = inbuf[in_left++]; } if constexpr (std::is_signed::value == true) { if (minus) x = -x; } } inline void wt(char c) { if (out_right > SZ - 32) flush(); outbuf[out_right++] = c; } inline void wt(bool b) { if (out_right > SZ - 32) flush(); outbuf[out_right++] = b ? '1' : '0'; } inline void wt(const std::string &s) { if (out_right + s.size() > SZ - 32) flush(); if (s.size() > SZ - 32){ fwrite(s.c_str(), 1, s.size(), stdout); return; } memcpy(outbuf + out_right, s.data(), sizeof(char) * s.size()); out_right += s.size(); } inline void wt(const char* s) { wt(std::string(s)); } template inline void wt(T x) { if (out_right > SZ - (int)sizeof(T) * 8) flush(); if (!x) { outbuf[out_right++] = '0'; return; } if constexpr (std::is_signed::value == true) { if (x < 0) outbuf[out_right++] = '-', x = -x; } constexpr int SZT = sizeof(T) * 8; int i = SZT - 4; char buf[SZT]; while (x >= 10000) { memcpy(buf + i, pre.num + (x % 10000) * 4, 4); x /= 10000; i -= 4; } if (x < 100) { if (x < 10) { outbuf[out_right] = '0' + x; ++out_right; } else { uint32_t q = (uint32_t(x) * 205) >> 11; uint32_t r = uint32_t(x) - q * 10; outbuf[out_right] = '0' + q; outbuf[out_right + 1] = '0' + r; out_right += 2; } } else { if (x < 1000) { memcpy(outbuf + out_right, pre.num + (x << 2) + 1, 3); out_right += 3; } else { memcpy(outbuf + out_right, pre.num + (x << 2), 4); out_right += 4; } } memcpy(outbuf + out_right, buf + i + 4, SZT - 4 - i); out_right += SZT - 4 - i; } } // namespace fastio namespace nachia{ struct CInStream{} cin; template inline CInStream& operator>>(CInStream& c, T& dest){ fastio::rd(dest); return c; } struct COutStream{ ~COutStream(){ atexit(fastio::flush); } } cout; template inline COutStream& operator<<(COutStream& c, const T& src){ fastio::wt(src); return c; } } // namespace nachia #line 1 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\vec.hpp" #include #include #include template struct seq; struct iotai; template struct seq_view{ using Ref = typename std::iterator_traits::reference; using Elem = typename std::iterator_traits::value_type; Iter a, b; Iter begin() const { return a; } Iter end() const { return b; } int size() const { return (int)(b-a); } seq_view(Iter first, Iter last) : a(first), b(last) {} seq_view sort() const { std::sort(a, b); return *this; } Ref& operator[](int x){ return *(a+x); } template> ret sorti(F f) const { ret x(iotai(0), iotai(size())); x().sort([&](int l, int r){ return f(a[l],a[r]); }); return x; } template> ret col() const { return ret(begin(), end()); } template seq_view sort(F f) const { std::sort(a, b, f); return *this; } Iter uni() const { return std::unique(a, b); } Iter lb(const Elem& x) const { return std::lower_bound(a, b, x); } Iter ub(const Elem& x) const { return std::upper_bound(a, b, x); } template Iter lb(const Elem& x, F f) const { return std::lower_bound(a, b, x, f); } template Iter ub(const Elem& x, F f) const { return std::upper_bound(a, b, x, f); } template Iter when_true_to_false(F f) const { if(a == b) return a; return std::lower_bound(a, b, *a, [&](const Elem& x, const Elem& y){ return f(x); }); } seq_view same(Elem x) const { return { lb(x), ub(x) }; } template auto map(F f) const { seq r; for(auto& x : *this) r.emp(f(x)); return r; } Iter max() const { return std::max_element(a, b); } Iter min() const { return std::min_element(a, b); } seq_view rev() const { std::reverse(a, b); return *this; } }; struct iotai { using i64 = long long; using Me = iotai; using value_type = i64; using iterator_category = std::random_access_iterator_tag; using difference_type = ptrdiff_t; using pointer = i64*; using reference = i64&; i64 x; iotai(i64 y) : x(y) {} i64 operator*() const { return x; } std::size_t operator-(Me a) const { return x - a.x; } Me operator++(){ return { (i64)(++x) }; } Me operator--(){ return { (i64)(--x) }; } Me operator++(int){ return { (i64)(x++) }; } Me operator--(int){ return { (i64)(x--) }; } Me operator+(std::size_t a) const { return { (i64)(x+a) }; } Me operator-(std::size_t a) const { return { (i64)(x-a) }; } static seq_view range(i64 l, i64 r){ return { Me{l}, Me{r} }; } }; template struct seq { using Base = typename std::vector; using Iter = typename Base::iterator; using CIter = typename Base::const_iterator; using View = seq_view; using CView = seq_view; seq(){} explicit seq(int n, const Elem& value = Elem()) : a(0 seq(I2 first, I2 last) : a(first, last) {} seq(std::initializer_list il) : a(std::move(il)) {} operator Base() const { return a; } Iter begin(){ return a.begin(); } CIter begin() const { return a.begin(); } Iter end(){ return a.end(); } CIter end() const { return a.end(); } int size() const { return a.size(); } seq sortunied(){ seq x = *this; x().sort(); x.a.erase(x().uni(), x.end()); return x; } Iter operator()(int x){ return (x < 0 ? a.end() : a.begin()) + x; } CIter operator()(int x) const { return (x < 0 ? a.end() : a.begin()) + x; } View operator()(int l, int r){ return { (*this)(l), (*this)(r) }; } CView operator()(int l, int r) const { return { (*this)(l), (*this)(r) }; } View operator()(){ return (*this)(0,size()); } CView operator()() const { return (*this)(0,size()); } Elem& operator[](int x){ return *((*this)(x)); } const Elem& operator[](int x) const { return *((*this)(x)); } Base& operator*(){ return a; } const Base& operator*() const { return a; } template seq& emp(Args &&... args){ a.emplace_back(std::forward(args) ...); return *this; } template seq& app(Range& x){ for(auto& v : a) emp(v); } Elem pop(){ Elem x = std::move(a.back()); a.pop_back(); return x; } Base a; }; #line 4 "..\\Main.cpp" using i64 = long long; #define rep(i,n) for(int i=0; i<(int)(n); i++) int main(){ using nachia::cin; using nachia::cout; int H, W; cin >> H >> W; seq> G; rep(y,H){ G.emp(W); rep(x,W) cin >> G[y][x]; } seq R(H), C(W); rep(y,H) cin >> R[y]; rep(x,W) cin >> C[x]; atcoder::mf_graph mf(H+W+2); int src = H + W; int snk = H + W + 1; i64 off = 0; rep(y,H){ i64 c = -R[y] * 2; rep(x,W) c += G[y][x]; if(c < 0){ mf.add_edge(src, y, -c); off -= c; } if(c > 0){ mf.add_edge(y, snk, c); } } rep(x,W){ i64 c = -C[x] * 2; rep(y,H) c += G[y][x]; if(c < 0){ mf.add_edge(src, H+x, -c); off -= c; } if(c > 0){ mf.add_edge(H+x, snk, c); } } rep(y,H) rep(x,W){ mf.add_edge(H+x, y, G[y][x]); mf.add_edge(y, H+x, G[y][x]); } i64 ans = mf.flow(src, snk); ans = (off - ans) / 2; cout << ans << '\n'; return 0; }