#line 2 "src/cp-template.hpp" #include using namespace std; using ll = long long; using ld = long double; using uint = unsigned int; using ull = unsigned long long; using i128 = __int128_t; template < class T > bool chmin(T& a, T b) { if(a > b) { a = b; return true; } return false; } template < class T > bool chmax(T& a, T b) { if(a < b) { a = b; return true; } return false; } #line 2 "src/utility/rep_itr.hpp" template < class T > struct itr { T i, d; constexpr itr(const T i) noexcept : i(i), d(1) {} constexpr itr(const T i, const T d) noexcept : i(i), d(d) {} void operator++() noexcept { i += d; } constexpr int operator*() const noexcept { return i; } constexpr bool operator!=(const itr x) const noexcept { return d > 0 ? i < x.i : i > x.i; } }; template < class T > struct rep { const itr< T > s, t; constexpr rep(const T t) noexcept : s(0), t(t) {} constexpr rep(const T s, const T t) noexcept : s(s), t(t) {} constexpr rep(const T s, const T t, const T d) noexcept : s(s, d), t(t, d) {} constexpr auto begin() const noexcept { return s; } constexpr auto end() const noexcept { return t; } }; template < class T > struct revrep { const itr < T > s, t; constexpr revrep(const T t) noexcept : s(t - 1, -1), t(-1, -1) {} constexpr revrep(const T s, const T t) noexcept : s(t - 1, -1), t(s - 1, -1) {} constexpr revrep(const T s, const T t, const T d) noexcept : s(t - 1, -d), t(s - 1, -d) {} constexpr auto begin() const noexcept { return s; } constexpr auto end() const noexcept { return t; } }; #line 2 "src/utility/io.hpp" namespace scanner { struct sca { template < class T > operator T() { T s; cin >> s; return s; } }; struct vec { int n; vec(int n) : n(n) {} template < class T > operator vector< T >() { vector< T > v(n); for(T& x : v) cin >> x; return v; } }; struct mat { int h,w; mat(int h, int w) : h(h), w(w) {} template < class T > operator vector< vector< T > >() { vector m(h, vector< T >(w)); for(vector< T >& v : m) for(T& x : v) cin >> x; return m; } }; struct speedup { speedup() { cin.tie(0); ios::sync_with_stdio(0); } } su; } scanner::sca in() { return scanner::sca(); } scanner::vec in(int n) { return scanner::vec(n); } scanner::mat in(int h, int w) { return scanner::mat(h, w); } namespace printer { void precision(int d) { cout << fixed << setprecision(d); } void flush() { cout.flush(); } } int print() { cout << '\n'; return 0; } template < class head, class... tail > int print(head&& h, tail&&... t) { cout << h; if(sizeof...(tail)) cout << ' '; return print(forward(t)...); } template < class T > int print(vector< T > a, char sep = ' ') { int n = a.size(); for(int i : rep(n)) cout << a[i] << (i != n - 1 ? sep : '\n'); return 0; } template < class T > int print(vector< vector< T > > a) { if(a.empty()) return 0; int h = a.size(), w = a[0].size(); for(int i : rep(h)) for(int j : rep(w)) cout << a[i][j] << (j != w - 1 ? ' ' : '\n'); return 0; } #line 2 "src/utility/key_val.hpp" template < class K, class V > struct key_val { K key; V val; key_val() {} key_val(K key, V val) : key(key), val(val) {} }; #line 2 "src/utility/vec_op.hpp" template < class T > key_val< int, T > max_of(const vector< T >& a) { int i = max_element(a.begin(), a.end()) - a.begin(); return {i, a[i]}; } template < class T > key_val< int, T > min_of(const vector< T >& a) { int i = min_element(a.begin(), a.end()) - a.begin(); return {i, a[i]}; } template < class T > T sum_of(const vector< T >& a) { T sum = 0; for(const T x : a) sum += x; return sum; } template < class T > vector freq_of(const vector< T >& a, T L, T R) { vector res(R - L); for(const T x : a) res[x - L]++; return res; } template < class T > vector freq_of(const vector< T >& a, T R) { return freq_of(a, T(0), R); } template < class T > struct prefix_sum { vector< T > s; prefix_sum(const vector< T >& a) : s(a) { s.insert(s.begin(), T(0)); for(int i : rep(a.size())) s[i + 1] += s[i]; } // [L, R) T sum(int L, int R) { return s[R] - s[L]; } }; #line 2 "A.cpp" template < class Cap > struct mf_graph { explicit mf_graph(int n) : n(n), g(n) {} int add_edge(int from, int to, Cap cap) { assert(0 <= from and from < n); assert(0 <= to and to < n); assert(0 <= cap); int m = pos.size(); int from_id = g[from].size(); int to_id = g[to].size() + (from == to); g[from].push_back(_edge{to, to_id, cap}); g[to].push_back(_edge{from, from_id, 0}); return m; } struct edge { int from, to; Cap cap, flow; }; edge get_edge(int i) { int m = pos.size(); assert(0 <= i and i < m); _edge e = g[pos[i].first][pos[i].second]; _edge r = g[e.to][e.rev]; return edge{pos[i].first, e.to, e.cap + r.cap, r.cap}; } vector edges() { int m = pos.size(); vector res(m); for(int i : rep(m)) res[i] = get_edge(i); return res; } void change_edge(int i, Cap cap, Cap flow) { int m = pos.size(); assert(0 <= i and i < m); assert(0 <= flow and flow <= cap); _edge& e = g[pos[i].first][pos[i].second]; _edge& r = g[e.to][e.rev]; e.cap = cap - flow; r.cap = flow; } Cap flow(int s, int t, Cap flow_limit) { assert(0 <= s and s < n); assert(0 <= t and t < n); assert(s != t); vector level(n), iter(n); auto bfs = [&]() { fill(level.begin(), level.end(), -1); level[s] = 0; queue q; q.push(s); while(not q.empty()) { int v = q.front(); q.pop(); for(_edge e : g[v]) { if(e.cap == 0 or level[e.to] >= 0) continue; level[e.to] = level[v] + 1; if(e.to == t) return; q.push(e.to); } } }; auto dfs = [&](auto self, int v, Cap up) { if(v == s) return up; Cap res = 0; int level_v = level[v]; for(int& i = iter[v]; i < int(g[v].size()); i++) { _edge& e = g[v][i]; if(level_v <= level[e.to] or g[e.to][e.rev].cap == 0) continue; Cap d = self(self, e.to, min(up - res, g[e.to][e.rev].cap)); if(d <= 0) continue; g[v][i].cap += d; g[e.to][e.rev].cap -= d; res += d; if(res == up) return res; } level[v] = n; return res; }; Cap flow = 0; while(flow < flow_limit) { bfs(); if(level[t] == -1) break; fill(iter.begin(), iter.end(), 0); Cap f = dfs(dfs, t, flow_limit - flow); if(f == 0) break; flow += f; } return flow; } Cap flow(int s, int t) { return flow(s, t, numeric_limits::max()); } vector min_cut(int s) { vector visited(n, 0); queue q; q.push(s); while(not q.empty()) { int p = q.front(); q.pop(); visited[p] = 1; for(_edge e : g[p]) { if(e.cap && not visited[e.to] == 0) { visited[e.to] = 1; q.push(e.to); } } } return visited; } private: int n; struct _edge { int to, rev; Cap cap; }; vector> pos; vector> g; }; int main() { int N = in(), S = in(), T = in(); mf_graph g(N + 2); const int src = N, dst = N + 1; ll inf = 1e18; for(int s : rep(S)) { int a = in(); a--; g.add_edge(src, a, inf); } for(int t : rep(T)) { int b = in(); b--; g.add_edge(b, dst, inf); } ll ans = 0; for(int i : rep(N)) { for(int j : rep(N)) { ll c = in(); g.add_edge(i, j, c); ans += c; } } print(ans / 2 - g.flow(src, dst)); }