#include using namespace std; template using vp = vector>; template using pque = priority_queue; template using lpque = priority_queue,greater>; using ll = long long; using pint = pair; using pll = pair; using pil = pair; using pli = pair; using vint = vector; using vll = vector; using qint = queue; using pqint = pque; using qll = queue; using pqll = pque; constexpr double PI = 3.141592653589793; constexpr int INTINF = (1<<30)-1; constexpr ll LLINF = (1LL<<62)-1; constexpr int MPRIME = 1000000007; constexpr int MPRIME9 = 998244353; constexpr ll MMPRIME = (1LL<<61)-1; constexpr char newl = '\n'; #define len length() #define pushb push_back #define fi first #define se second #define all(name) name.begin(),name.end() #define rall(name) name.rbegin(),name.rend() #define gsort(vbeg,vend) sort(vbeg,vend,greater<>()) template struct matrix{ private: vector> mat; public: matrix() : matrix(0,0) {} matrix(int h, int w) { resize(h,w); } matrix(int h, int w, T init) { resize(h,w,init); } void resize(int h, int w) { mat=vector>(h,vector(w)); } void resize(int h, int w, T init) { mat=vector>(h,vector(w,init)); }; void in() { for(int i=0; i>mat[i][j]; } } void out() { for(int i=0; i &operator[](int idx) { assert(0<=idx && idx inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } template inline void init(T& v) { for(auto &a: v) cin>>a; } template inline void init(vector>& v) { for(auto &a: v) cin>>a.first>>a.second; } template inline void init(T& v, N n) { v.resize(n); for(auto &a: v) cin>>a; } template inline void init(vector>& v, N n) { v.resize(n); for(auto &a: v) cin>>a.first>>a.second; } template inline void out(T a) { cout< inline void out(T a, U... alist) { cout<(alist)...); } template void resiz(N n) { //empty } template void resiz(N n, T&& hd, U&&... tl) { hd.resize(n); resiz(n,forward(tl)...); } long long binpow(long long a, long long ex, long long p=MMPRIME) { long long res = 1; while(ex > 0) { if(ex & 1) (res*=a) %= p; ex>>=1; (a*=a) %= p; } return res; } struct maxflow { private: struct edge { int next; int rev; long long cap; edge(int next, int rev, long long cap) : next(next), rev(rev), cap(cap) {} }; const int vnum; vector> G; vector used; public: maxflow(int N) : vnum(N), G(N), used(N) {} void add(int from, int to, long long cap) { G[from].push_back(edge(to, G[to].size(), cap)); G[to].push_back(edge(from, G[from].size()-1, 0)); } private: long long dfs(int s, int t, long long flow) { if(s == t) return flow; used[s] = true; for(edge &ed : G[s]) { if(!used[ed.next] && ed.cap>0) { long long captmp = dfs(ed.next, t, min(flow,ed.cap)); if(captmp > 0) { ed.cap -= captmp; G[ed.next][ed.rev].cap += captmp; return captmp; } } } return 0LL; } public: long long solve(int s, int t) { long long res = 0; while(1) { used.assign(vnum, false); long long restmp = dfs(s, t, (1LL<<62)-1); if(restmp == 0) return res; res += restmp; } } }; int W,N,M; vector J,C; matrix X; void input() { cin>>W>>N; J.resize(N); for(int &j: J) cin>>j; cin>>M; C.resize(M); for(int &c: C) cin>>c; X.resize(N,M,true); for(int i=0; i>Q; for(int j=0; j>x; X[--x][i] = false; } } } void solve() { maxflow mf(N+M+2); for(int i=0; i