#include using namespace std; #define ALL(x) begin(x),end(x) #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<bool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(b ostream &operator<<(ostream &os,const vector&v){ for(int i=0;i<(int)v.size();i++) os< istream &operator>>(istream &is,vector&v){ for(T &x:v)is>>x; return is; } // O(F E \log V) template struct PrimalDual{ struct Edge{ int dst; Flow cap; Cost cost; int rev; Edge(int dst,Flow cap,Cost cost,int rev): dst(dst),cap(cap),cost(cost),rev(rev){} }; vector> G; vector h,dist; vector prevv,preve; PrimalDual(int n):G(n),h(n),dist(n),prevv(n),preve(n){} void add_edge(int u,int v,Flow cap,Cost cost){ int e=G[u].size(); int r=(u==v?e+1:G[v].size()); G[u].emplace_back(v,cap,cost,r); G[v].emplace_back(u,0,-cost,e); } Cost residual_cost(int src,Edge &e){ return e.cost+h[src]-h[e.dst]; } void dijkstra(int s){ struct P{ Cost first; int second; P(Cost first,int second):first(first),second(second){} bool operator<(const P&a) const{return first>a.first;} }; priority_queue

pq; dist[s]=0; pq.emplace(dist[s],s); while(!pq.empty()){ P p=pq.top();pq.pop(); int v=p.second; if(dist[v] init=[](decltype(h) &p){ fill(p.begin(),p.end(),0); }){ res=0; init(h); const Cost INF = numeric_limits::max(); while(f>0){ fill(dist.begin(),dist.end(),INF); dijkstra(s); if(dist[t]==INF) return false; for(int v=0;v<(int)h.size();v++) if(dist[v]>N>>K; PrimalDual flow(N+N+40); int src=N+N,sink=N+N+1; flow.add_edge(src,0,K,0); flow.add_edge(N+N-1,sink,K,0); rep(i,N){ flow.add_edge(i,i+N,K,0); if(i+1 A(N); vector h(N+N+40,0); rep(i,N){ int t;cin>>A[i]>>t; rep(j,t){ int a;cin>>a;a--; flow.add_edge(a+N,i,1,-(A[i]-A[a])); chmin(h[a+N],h[i]-(A[i]-A[a])); } } flow.add_edge(src,sink,128741,0); auto init=[&](auto &wa)->void{ wa=move(h); }; bool ok=false; int mx=K*N; int res=flow.build(src,sink,mx,init); cout<<-flow.get_cost()<