#include using namespace std; using ll=long long; //#define int ll #define rng(i,a,b) for(int i=int(a);i=int(a);i--) #define per(i,b) gnr(i,0,b) #define pb push_back #define eb emplace_back #define a first #define b second #define bg begin() #define ed end() #define all(x) x.bg,x.ed #define si(x) int(x.size()) #ifdef LOCAL #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "< bool chmax(t&a,u b){if(a bool chmin(t&a,u b){if(b using vc=vector; template using vvc=vc>; using pi=pair; using vi=vc; template ostream& operator<<(ostream& os,const pair& p){ return os<<"{"< ostream& operator<<(ostream& os,const vc& v){ os<<"{"; for(auto e:v)os< void dmpr(ostream&os,const T&t,const Args&... args){ os< ostream& operator<<(ostream&os,const array&a){ return os<(all(a)); } template void print_tuple(ostream&,const T&){ } template void print_tuple(ostream&os,const T&t){ if(i)os<<","; os<(t); print_tuple(os,t); } template ostream& operator<<(ostream&os,const tuple&t){ os<<"{"; print_tuple<0,tuple,Args...>(os,t); return os<<"}"; } template void print(t x,int suc=1){ cout<>i; return i; } vi readvi(int n,int off=0){ vi v(n); rep(i,n)v[i]=read()+off; return v; } pi readpi(int off=0){ int a,b;cin>>a>>b; return pi(a+off,b+off); } template void print(const vector&v,int suc=1){ rep(i,v.size()) print(v[i],i==int(v.size())-1?suc:2); } string readString(){ string s; cin>>s; return s; } template T sq(const T& t){ return t*t; } //#define CAPITAL void yes(bool ex=true){ #ifdef CAPITAL cout<<"YES"<<"\n"; #else cout<<"Yes"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void no(bool ex=true){ #ifdef CAPITAL cout<<"NO"<<"\n"; #else cout<<"No"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void possible(bool ex=true){ #ifdef CAPITAL cout<<"POSSIBLE"<<"\n"; #else cout<<"Possible"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void impossible(bool ex=true){ #ifdef CAPITAL cout<<"IMPOSSIBLE"<<"\n"; #else cout<<"Impossible"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } constexpr ll ten(int n){ return n==0?1:ten(n-1)*10; } const ll infLL=LLONG_MAX/3; #ifdef int const int inf=infLL; #else const int inf=INT_MAX/2-100; #endif int topbit(signed t){ return t==0?-1:31-__builtin_clz(t); } int topbit(ll t){ return t==0?-1:63-__builtin_clzll(t); } int botbit(signed a){ return a==0?32:__builtin_ctz(a); } int botbit(ll a){ return a==0?64:__builtin_ctzll(a); } int popcount(signed t){ return __builtin_popcount(t); } int popcount(ll t){ return __builtin_popcountll(t); } bool ispow2(int i){ return i&&(i&-i)==i; } ll mask(int i){ return (ll(1)< void mkuni(vc&v){ sort(all(v)); v.erase(unique(all(v)),v.ed); } ll rand_int(ll l, ll r) { //[l, r] #ifdef LOCAL static mt19937_64 gen; #else static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count()); #endif return uniform_int_distribution(l, r)(gen); } template void myshuffle(vc&a){ rep(i,si(a))swap(a[i],a[rand_int(0,i)]); } template int lwb(const vc&v,const t&a){ return lower_bound(all(v),a)-v.bg; } vvc readGraph(int n,int m){ vvc g(n); rep(i,m){ int a,b; cin>>a>>b; //sc.read(a,b); a--;b--; g[a].pb(b); g[b].pb(a); } return g; } vvc readTree(int n){ return readGraph(n,n-1); } using int128=__int128_t; using uint128=unsigned __int128_t; //-が来た場合はまだわからん istream& operator>>(istream&is,int128&res){ res=0; string s;is>>s; int head=0; int128 w=1; if(s[0]=='_'){ w=-1; head++; } while(head>64)); } int128 gcd(int128 a,int128 b){ if(a<0)a=-a; if(b<0)b=-b; if(a==0)return b; if(b==0)return a; int128 s=botbit(a|b); a>>=botbit(a); do{ b>>=botbit(b); if(a>b)swap(a,b); b-=a; }while(b); return a< struct maxflow{ struct E{ int to,nx; d cap; }; vc es; vi head,q; vc itr,lv; int curt; maxflow(int n):head(n,-1),q(n),itr(n),lv(n),curt(0){} int ae(int s,int t,d c,d c2=0){ int pres=head[s]; int pret=head[t]; head[s]=si(es); es.pb({t,pres,c}); head[t]=si(es); es.pb({s,pret,c2}); return head[s]; } void bfs(int s,int t=-1){ lv[s]=pi(0,curt); int l=0,r=0; q[r++]=s; while(l0&&lv[e.to].b0&&lv[e.to].a==lv[v].a-1&&lv[e.to].b==curt){ d a=dfs(e.to,t,min(f,rev.cap)); if(a>0){ rev.cap-=a; e.cap+=a; res+=a; f-=a; if(f<=0)break; } } itr[v].a=e.nx; } return res; } d calc(int s,int t,d mx=inf){ d f=0; while(f struct costscaling{ struct E{ int to,rev; captype cap; costtype cost; }; int n; costtype eps; vvc g; vc idx; vi itr,q; vc inq,vis; vc fl,off; vc p; maxflow mf; anstype ans; costscaling(int nn):n(nn),g(n),itr(n),inq(n),vis(n),fl(n),p(n),mf(n+2),ans(0){} void ae(int s,int t,captype l,captype r,costtype c){ assert(l<=r); if(s==t){ idx.eb(-1,-1); captype f=c>0?l:r; ans+=anstype(c)*f; off.pb(f); }else{ c*=(n+1); idx.eb(s,si(g[s])); off.pb(r); fl[s]-=l; fl[t]+=l; g[s].pb({t,si(g[t]),r-l,c}); g[t].pb({s,si(g[s])-1,0,-c}); } mf.ae(s,t,r-l); } void add_excess(int v,captype c){ fl[v]+=c; } void add_demand(int v,captype c){ fl[v]-=c; } costtype getcost(int v,const E&e){ return e.cost-p[e.to]+p[v]; } void addq(int v){ if(fl[v]>0&&!inq[v]){ q.pb(v); inq[v]=true; } } void push(int v,E&e,captype a){ int to=e.to,j=e.rev; assert(0<=a); assert(a<=e.cap); e.cap-=a; g[to][j].cap+=a; fl[v]-=a; fl[to]+=a; addq(to); } void relabel(int v){ p[v]=numeric_limits::min()/2; for(const auto&e:g[v]){ if(e.cap>0){ chmax(p[v],-eps-e.cost+p[e.to]); } } itr[v]=0; } bool dfs(int v,int dep,captype come){ if(vis[v])return false; vis[v]=true; if(fl[v]<0||dep==4){ vis[v]=false; return true; }else{ while(itr[v]0){ f+=fl[i]; mf.ae(n,i,fl[i]); }else if(fl[i]<0){ mf.ae(i,n+1,-fl[i]); } captype did=mf.calc(n,n+1,f); if(did0)chmax(eps,-getcost(v,e)); if(eps<=1)break; eps=max(eps/8,costtype(1)); bool need=true; rep(_,5){ bool upd=false; rep(v,n)for(const auto&e:g[v])if(e.cap>0){ if(chmin(p[e.to],p[v]+e.cost+eps)) upd=true; } if(!upd){ need=false; break; } } if(!need)continue; rep(v,n)for(auto&e:g[v])if(getcost(v,e)<0) push(v,e,e.cap); q.clear(); rep(i,n){ itr[i]=0; inq[i]=false; } int qb=0; rep(i,n)addq(i); while(qb0)dfs(v,0,0); /*while(fl[v]>0){ if(itr[v]==si(g[v])) relabel(v); while(itr[v]0)assert(getcost(v,e)>=-1); rep(v,n)for(auto&e:g[v])e.cost/=(n+1); return true; } pair> get_solution(){ rep(i,si(off))if(idx[i].a!=-1){ const auto&e=g[idx[i].a][idx[i].b]; off[i]-=e.cap; ans+=anstype(e.cost)*off[i]; } return mp(ans,off); } vc get_potential(){ rep(i,n)p[i]/=(n+1); rep(_,n+1){ bool upd=false; rep(v,n)for(const auto&e:g[v])if(e.cap>0){ if(chmin(p[e.to],p[v]+e.cost)) upd=true; } if(!upd)break; assert(_ cs(n); rep(i,n)cs.add_excess(i,0); rep(i,m){ int s,t,l,u,c;//cin>>s>>t>>l>>u>>c; s=rand_int(0,n-1); t=rand_int(0,n-1); l=rand_int(-ten(9),ten(9)); u=rand_int(-ten(9),ten(9)); if(u f; tie(ans,f)=cs.get_solution(); vc p=cs.get_potential(); cout<>n>>m; ll a[3030], b[3030], c[3030]; using P=pair; vector

v(n); for(int i=0; i>a[i]>>b[i]>>c[i]; if(a[i]>c[i]) swap(a[i], c[i]); v[i]=P(a[i], c[i]); } sort(v.begin(), v.end()); vector

w(n); for(int i=0; i cs(4*n); for(int i=0; i0){ cs.ae(i, 2*n+p-1, 0, 1, MAX-b[i]); } } for(int i=0; i=m) cout<<"KADOMATSU!"<>t;rep(_,t) //test(); slv(); }