#include <bits/stdc++.h>using namespace std ;typedef pair < int , int > pii ;#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 105 ;const int INF = 0x3f3f3f3f ;struct Node {	vector < pii > G ;	int val ;	bool operator < ( const Node& a ) const {		return val > a.val ;	}} ;Node a[MAXN] ;int minv[MAXN][MAXN] ;int pre[MAXN] ;int tmp[MAXN][MAXN] ;int ans ;int n , m , k ;void dfs ( int cur , int num ) {	int val = 0 ;	for ( int i = 1 ; i <= n ; ++ i ) {		if ( pre[i] == INF ) {			val = INF ;			break ;		}		val += pre[i] ;	}	if ( val < ans ) ans = val ;	int tot = 0 ;	for ( int i = 1 ; i <= n ; ++ i ) {		if ( pre[i] == INF && minv[cur][i] == INF ) return ;		tot += min ( pre[i] , minv[cur][i] ) ;	}	if ( tot >= ans ) return ;	if ( num >= k ) return ;	for ( int i = cur ; i <= m ; ++ i ) {		for ( int j = 1 ; j <= n ; ++ j ) {			tmp[num][j] = pre[j] ;		}//		vector < pii > tmp ;//		int c = 0 , v = 0 ;/*		for ( int j = 0 ; j < a[i].G.size () ; ++ j ) {			int x = a[i].G[j].first ;			tmp.push_back ( pii ( x , pre[x] ) ) ;			if ( a[i].G[j].second < pre[x] ) {				if ( pre[x] != INF ) v -= pre[x] ;				else ++ c ;				pre[x] = a[i].G[j].second ;				v += pre[x] ;			}		}*/		for ( int j = 0 ; j < a[i].G.size () ; ++ j ) {			int x = a[i].G[j].first ;			pre[x] = min ( pre[x] , a[i].G[j].second ) ;		}		dfs ( i + 1 , num + 1 ) ;		for ( int j = 1 ; j <= n ; ++ j ) {			pre[j] = tmp[num][j] ;			/*			int x = tmp[j].first ;			pre[x] = tmp[j].second ;			*/		}	}}void solve () {	ans = INF ;	for ( int i = 1 ; i <= m ; ++ i ) {		a[i].G.clear () ;		a[i].val = 0 ;	}	for ( int i = 1 ; i <= n ; ++ i ) {		int x , p , y , q ;		scanf ( "%d%d%d%d" , &x , &p , &y , &q ) ;		a[x].val ++ ;		a[y].val ++ ;		if ( p < q ) a[x].val += 2 ;		else a[y].val += 2 ;		a[x].G.push_back ( pii ( i , p ) ) ;		a[y].G.push_back ( pii ( i , q ) ) ;	}	sort ( a + 1 , a + m + 1 ) ;	for ( int i = 1 ; i <= n ; ++ i ) {		minv[m + 1][i] = INF ;		pre[i] = INF ;	}	for ( int i = m ; i >= 1 ; -- i ) {		for ( int j = 1 ; j <= n ; ++ j ) {			minv[i][j] = minv[i + 1][j] ;		}		for ( int j = 0 ; j < a[i].G.size () ; ++ j ) {			int x = a[i].G[j].first , v = a[i].G[j].second ;			minv[i][x] = min ( minv[i][x] , v ) ;		}	}	dfs ( 1 , 0 ) ;	printf ( "%d\n" , ans == INF ? -1 : ans ) ;}int main () {	while ( ~scanf ( "%d%d%d" , &n , &m , &k ) ) solve () ;	return 0 ;}

#include<stdio.h>#include<algorithm>#include<math.h>#include<string.h>#include<string>#include<vector>#include<set>#include<map>#include<queue>#include<time.h>#include<assert.h>#include<iostream>using namespace std;typedef long long LL;typedef pair<int,int>pi;const int Maxn=4040;char s[Maxn];int len1[Maxn],len2[Maxn],L[Maxn],R[Maxn];int n;int sta[Maxn];int top;int numlen[Maxn*20];int main(){	for(int i=1;i<Maxn*20;i++){		numlen[i]=numlen[i/10]+1;	}	while(scanf("%s",s)!=EOF){		n=strlen(s);		for(int i=0;i<n;i++)len1[i]=len2[i]=1;		while(1){			top=0;			int curlen=0;			for(int i=0;i<n;i++){				if(s[i]==‘(‘){					curlen+=len1[i]+len2[i]+2;					L[i]=curlen;					sta[top++]=i;				}				else{					R[sta[top-1]]=curlen;					top--;				}			}			bool flag=1;			for(int i=0;i<n;i++){				if(s[i]!=‘(‘)continue;				if(numlen[L[i]]!=len1[i]||numlen[R[i]]!=len2[i]){flag=0;}				len1[i]=numlen[L[i]];				len2[i]=numlen[R[i]];			}			if(flag)break;		}		for(int i=0;i<n;i++){			if(s[i]==‘(‘){				printf("%d,%d:",L[i],R[i]);			}		}		puts("");	}	return 0;}

#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;typedef long long ll;const ll inf=1e16;const int N=15;int n,m,i,j,k,S,a[N],b[N],c[N],A[1<<N],B[1<<N],D[1<<N];ll C[1<<N],ans,f[16][1<<N],cost[1<<N],tmp;inline void up(ll&a,ll b){if(a>b)a=b;}int main(){  scanf("%d%d",&n,&m);  for(i=0;i<n;i++)scanf("%d%d%d",&a[i],&b[i],&c[i]);  for(S=1;S<1<<n;S++){    for(i=0;i<n;i++)if(S>>i&1){      A[S]=max(A[S],a[i]);      B[S]=max(B[S],b[i]);      C[S]+=1LL*a[i]*b[i]*c[i];      D[S]+=c[i];    }    cost[S]=1LL*A[S]*B[S]*D[S]-C[S];  }  for(i=0;i<=m;i++)for(j=0;j<1<<n;j++)f[i][j]=inf;  up(f[0][0],0);  for(i=1;i<=m;i++)for(j=0;j<1<<n;j++){    tmp=inf;    for(k=j;k;k=(k-1)&j)if(f[i-1][j-k]<inf){      up(tmp,f[i-1][j-k]+cost[k]);    }    f[i][j]=tmp;  }  ans=inf;  for(i=0;i<=m;i++)up(ans,f[i][(1<<n)-1]);  printf("%lld",ans);}

#include<bits/stdc++.h>using namespace std;const int Maxn=2502;const double Inf=1e50;int n,k;double dp[2520][2520];int s[Maxn],p[Maxn],id[Maxn];int pre[Maxn],fin[Maxn];vector<int>G[Maxn];int dfs_t;void dfs(int u){	pre[u]=++dfs_t;	id[dfs_t]=u;	for(int i=0;i<G[u].size();i++){		int v=G[u][i];		dfs(v);	}	fin[u]=dfs_t;}double check(double x){	for(int i=1;i<=n+1;i++){		for(int j=0;j<=k;j++){			dp[i][j]=-1e60;		}	}	dp[1][0]=0;	for(int i=1;i<=n;i++){		double w=p[id[i]]-s[id[i]]*x;		for(int j=0;j<=k;j++){			if(dp[i][j]<-Inf)continue;			if(j<k){				dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+w);			}			dp[fin[id[i]]+1][j]=max(dp[fin[id[i]]+1][j],dp[i][j]);		}	}	return dp[n+1][k];}int main(){	while(scanf("%d%d",&k,&n)!=EOF){		for(int i=1;i<=n;i++)pre[i]=0,G[i].clear();		for(int i=1;i<=n;i++){			int f;			scanf("%d%d%d",s+i,p+i,&f);			G[f].push_back(i);		}		dfs_t=0;		for(int i=1;i<=n;i++){			if(!pre[i])dfs(i);		}		double l=0,r=10200;		for(int i=0;i<30;i++){			double mid=(l+r)/2.;			double tp=check(mid);			if(tp>0)l=mid;			else r=mid;		}		printf("%.3f\n",r);	}}

#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;const int N=2200000;int n,i,j,k;char s[N];int pos[N];struct comp{  double r,i;  comp(double _r=0,double _i=0){r=_r,i=_i;}  comp operator+(const comp&x){return comp(r+x.r,i+x.i);}  comp operator-(const comp&x){return comp(r-x.r,i-x.i);}  comp operator*(const comp&x){return comp(r*x.r-i*x.i,r*x.i+i*x.r);}  comp conj(){return comp(r,-i);}}A[N],B[N];const double pi=acos(-1.0);void FFT(comp a[],int n,int t){  for(int i=1;i<n;i++)if(i<pos[i])swap(a[i],a[pos[i]]);  for(int d=0;(1<<d)<n;d++){    int m=1<<d,m2=m<<1;    double o=pi*2/m2*t;comp _w(cos(o),sin(o));    for(int i=0;i<n;i+=m2){      comp w(1.0);      for(int j=0;j<m;j++){        comp&A=a[i+j+m],&B=a[i+j],t=w*A;        A=B-t;B=B+t;w=w*_w;      }    }  }  if(t==-1)for(int i=0;i<n;i++)a[i].r/=n;}int main(){  scanf("%s",s+1);  n=strlen(s+1);  for(i=1;i<=n;i++)if(s[i]==‘A‘)A[i].r=1;  else A[n-i].i=1;  k=1048576*2;  j=__builtin_ctz(k)-1;  for(i=0;i<k;i++)pos[i]=pos[i>>1]>>1|((i&1)<<j);  FFT(A,k,1);  for(i=0;i<k;i++){    j=(k-i)&(k-1);    B[i]=(A[i]*A[i]-(A[j]*A[j]).conj())*comp(0,-0.25);  }  FFT(B,k,-1);  for(i=1;i<n;i++)printf("%d\n",(int)(B[i+n].r+0.5));}

#include<cstdio>const int P=1000000007;int n,w,h,i,j,k,ans,f[105][10005];inline void up(int&x,int y){  x+=y;  if(x>=P)x-=P;}int main(){  scanf("%d%d%d",&n,&w,&h);  f[0][0]=1;  for(i=1;i<=w;i++)    for(j=0;j<=n;j++)if(f[i-1][j])      for(k=0;k<=h;k++){        if(j+k>n)break;        up(f[i][j+k],f[i-1][j]);      }  for(i=0;i<=n;i++)up(ans,f[w][i]);  for(i=0;i<=h;i++)if(i*w<=n)ans--;  ans+=P;  ans%=P;  printf("%d",ans);}

#include <bits/stdc++.h>using namespace std ;typedef long long LL ;typedef pair < int , int > pii ;typedef pair < LL , LL > pll ;#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 1005 ;map < pii , int > mp1 ;map < pair < pll , LL > , int > mp2 ;map < pair < pll , LL > , int > mp3 ;int x[MAXN] , y[MAXN] , num[MAXN * MAXN] ;pii pt[MAXN * MAXN] ;LL dis[MAXN][MAXN] ;int n , p ;pair < pll , LL > calc ( int x1 , int x2 , int y1 , int y2 ) {	if ( x1 == x2 ) {		LL A = 0 ;		LL B = 1 ;		LL C = - ( y1 + y2 ) / 2 ;		return make_pair ( pii ( A , B ) , C ) ;	}	if ( y1 == y2 ) {		LL A = 1 ;		LL B = 0 ;		LL C = - ( x1 + x2 ) / 2 ;		return make_pair ( pii ( A , B ) , C ) ;	}	LL A = y2 - y1 ;	LL B = x1 - x2 ;	LL g = 0 ;	LL C = - B * ( x1 + x2 ) / 2 + A * ( y1 + y2 ) / 2 ;	swap ( A , B ) ;	B = -B ;	g = 0 ;	if ( A ) {		if ( A < 0 ) A = -A , B = -B , C = -C ;	} else {		if ( B < 0 ) A = -A , B = -B , C = -C ;	}	if ( A ) g = g ? __gcd ( g , abs ( A ) ) : abs ( A ) ;	if ( B ) g = g ? __gcd ( g , abs ( B ) ) : abs ( B ) ;	if ( C ) g = g ? __gcd ( g , abs ( C ) ) : abs ( C ) ;	if ( g ) A /= g , B /= g , C /= g ;	return make_pair ( pll ( A , B ) , C ) ;}int get_id ( pair < pll , LL > t ) {	if ( mp2.count ( t ) ) return mp2[t] ;	mp2[t] = ++ p ;	num[p] = 0 ;	return p ;}LL get_dis ( int x , int y ) {	return 1LL * x * x + 1LL * y * y ;}void solve () {	p = 0 ;	mp1.clear () ;	mp2.clear () ;	for ( int i = 1 ; i <= n ; ++ i ) {		scanf ( "%d%d" , &x[i] , &y[i] ) ;	}	for ( int i = 1 ; i <= n ; ++ i ) {		for ( int j = 1 ; j <= n ; ++ j ) {			dis[i][j] = get_dis ( x[i] - x[j] , y[i] - y[j] ) ;		}	}	for ( int i = 1 ; i <= n ; ++ i ) {		mp1[pii ( x[i] + x[i] , y[i] + y[i] )] ++ ;		for ( int j = 1 ; j < i ; ++ j ) {			mp1[pii ( x[i] + x[j] , y[i] + y[j] )] += 2 ;			int id = get_id ( calc ( x[i] * 2 , x[j] * 2 , y[i] * 2 , y[j] * 2 ) ) ;			num[id] += 2 ;			pt[id] = pii ( i , j ) ;		}	}	int ans = MAXN ;	for ( map < pii , int > :: iterator it = mp1.begin () ; it != mp1.end () ; ++ it ) {		ans = min ( ans , n - it->second ) ;	}	for ( int i = 1 ; i <= p ; ++ i ) {		int xx = pt[i].first , yy = pt[i].second ;		int cnt = 0 ;		for ( int j = 1 ; j <= n ; ++ j ) {			if ( dis[xx][j] == dis[yy][j] ) ++ cnt ;		}		ans = min ( ans , n - cnt - num[i] ) ;	}	for ( int i = 1 ; i <= n ; ++ i ) {		for ( int j = 1 ; j <= n ; ++ j ) if ( i != j ) {			LL A = y[j] - y[i] ;			LL B = x[i] - x[j] ;			LL C = x[j] * y[i] - x[i] * y[j] ;			int cnt = 0 ;			for ( int k = 1 ; k <= n ; ++ k ) {				if ( A * x[k] + B * y[k] + C == 0 ) ++ cnt ;			}			ans = min ( ans , n - cnt ) ;		}	}	printf ( "%d\n" , ans ) ;}int main () {	while ( ~scanf ( "%d" , &n ) ) solve () ;	return 0 ;}

#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;const int N=220000;int n,i,j,x,y,g[N],v[N<<1],nxt[N<<1],ed;long long ans;int size[N],f[N],d[N],son[N],top[N];inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}void dfs(int x){  size[x]=1;  for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x]){    f[v[i]]=x,d[v[i]]=d[x]+1;    dfs(v[i]),size[x]+=size[v[i]];    if(size[v[i]]>size[son[x]])son[x]=v[i];  }}void dfs2(int x,int y){  top[x]=y;  if(son[x])dfs2(son[x],y);  for(int i=g[x];i;i=nxt[i])if(v[i]!=son[x]&&v[i]!=f[x])dfs2(v[i],v[i]);}inline int lca(int x,int y){  for(;top[x]!=top[y];x=f[top[x]])if(d[top[x]]<d[top[y]])swap(x,y);  return d[x]<d[y]?d[x]:d[y];}int main(){  scanf("%d",&n);  for(i=1;i<n;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x);  dfs(1);  dfs2(1,1);  for(i=1;i<=n;i++)for(j=i+i;j<=n;j+=i){    ans+=d[i]+d[j]-2*lca(i,j)+1;  }  printf("%lld",ans);}

#include<bits/stdc++.h>using namespace std;const int Maxn=1000020;typedef long long LL;char s[1000200];int n,m,q;int debug;set<int>sx[Maxn],sy[Maxn];int d[Maxn],op[Maxn];int di[4][2]={{-1,0},{0,1},{1,0},{0,-1}};int getop(char* ss){	if(ss[0]==‘u‘)return 0;	if(ss[0]==‘r‘)return 1;	if(ss[0]==‘d‘)return 2;	if(ss[0]==‘l‘)return 3;	return -1;}LL L,R;char ask(int wh,int ty,int loc){	if(!ty)swap(loc,wh);	return s[wh*m+loc];}void solve(set<int>&S,int st,int ed,LL tl,int wh,int ty){	int l=st,r=ed;	if(l>r)swap(l,r);	set<int>::iterator it=S.lower_bound(l);	for(;it!=S.end()&&((*it)<=r);){		char c=ask(wh,ty,*it);		if(ty==0){			sx[*it].erase(sx[*it].lower_bound(wh));		}		else{			sy[*it].erase(sy[*it].lower_bound(wh));		}		//if(debug)printf("wh=%d ty=%d loc=%d c=%c\n",wh,ty,*it,c);		if(c==‘#‘)L=max(L,tl-abs((*it)-st));		else R=min(R,tl-abs((*it)-st)-1);		S.erase(it++);	}}int main(){	while(scanf("%d%d%d",&n,&m,&q)!=EOF){		for(int i=0;i<n;i++){			scanf("%s",s+(i*m));		}		//printf("%s\n",s);		//printf("%c\n",s[35]);		for(int i=0;i<n;i++){			sx[i].clear();			for(int j=0;j<m;j++)sx[i].insert(j);		}		for(int i=0;i<m;i++){			sy[i].clear();			for(int j=0;j<n;j++)sy[i].insert(j);		}		for(int i=0;i<q;i++){			char tmp[10];			scanf("%s%d",tmp,d+i);			op[i]=getop(tmp);		}		int curx=n-1,cury=0;		LL tl=1;		for(int i=0;i<q;i++){			curx+=di[op[i]][0]*d[i];			cury+=di[op[i]][1]*d[i];			tl+=d[i];		}		L=0,R=tl;		//printf("curx=%d cury=%d tl=%lld\n",curx,cury,tl);		for(int i=q-1;i>=0;i--){			int top=(op[i]+2)%4;			if(i==1)debug=1;else debug=0;			int nx=curx+di[top][0]*d[i],ny=cury+di[top][1]*d[i];			//printf("ny=%d\n",ny);			if(top==0||top==2)solve(sy[ny],curx,nx,tl,ny,0);			else solve(sx[nx],cury,ny,tl,nx,1);			tl-=d[i];			curx=nx;			cury=ny;			//printf("i=%d L=%lld R=%lld\n",i,L,R);		}		for(int i=0;i<n&&L<=R;i++){			for(set<int>::iterator it=sx[i].begin();it!=sx[i].end();it++){				if(ask(i,1,*it)==‘#‘){					L=R+1;					break;				}			}		}		if(L>R)puts("-1 -1");		else printf("%lld %lld\n",L,R);	}}

#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;typedef long long ll;const ll inf=1e16;const int N=200010;inline void up(ll&a,ll b){if(a>b)a=b;}int n,i,x,y,z,a[N],g[N],v[N<<1],w[N<<1],nxt[N<<1],ok[N<<1],ed;ll ans[N],fin,d[N];int f[N],son[N],all,now;inline void add(int x,int y,int z){v[++ed]=y;w[ed]=z;ok[ed]=1;nxt[ed]=g[x];g[x]=ed;}struct P{ll k,b;P(){}P(ll _x,ll _y){k=_x,b=_y;}}A[N],q[N];int B[N],m;inline double pos(const P&a,const P&b){return ((double)(b.b-a.b))/((double)(a.k-b.k));}inline bool cmpA(const P&a,const P&b){  if(a.k==b.k)return a.b<b.b;  return a.k>b.k;}inline bool cmpB(int x,int y){return a[x]<a[y];}void findroot(int x,int y){  son[x]=1;f[x]=0;  for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=y){    findroot(v[i],x);    son[x]+=son[v[i]];    if(son[v[i]]>f[x])f[x]=son[v[i]];  }  if(all-son[x]>f[x])f[x]=all-son[x];  if(f[x]<f[now])now=x;}void dfs(int x,int y,ll z){  m++;  d[x]=z;  A[m]=P(a[x],z);  B[m]=x;  for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=y)dfs(v[i],x,z+w[i]);}inline ll cal(int x,int y){  return q[y].k*a[x]+d[x]+q[y].b;}void solve(int x){  int i,h=1,t;  m=0;  dfs(x,0,0);  sort(A+1,A+m+1,cmpA);  sort(B+1,B+m+1,cmpB);  q[t=1]=A[1];  for(i=2;i<=m;i++)if(A[i].k!=A[i-1].k){    while(t>1&&pos(q[t-1],q[t])>pos(q[t],A[i]))t--;    q[++t]=A[i];  }  for(i=1;i<=m;i++){    while(h<t&&cal(B[i],h)>cal(B[i],h+1))h++;    ans[B[i]]=min(ans[B[i]],cal(B[i],h));  }  for(i=g[x];i;i=nxt[i])if(ok[i]){    ok[i^1]=0;    f[0]=all=son[v[i]];    findroot(v[i],now=0);    solve(now);  }}int main(){  scanf("%d",&n);  for(i=1;i<=n;i++)scanf("%d",&a[i]);  for(ed=i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z);  for(i=1;i<=n;i++)ans[i]=inf;  f[0]=all=n;  findroot(1,now=0);  solve(now);  for(i=1;i<=n;i++)fin+=ans[i];  printf("%lld",fin);}