#include<bits/stdc++.h>
using namespace std;

const int N = 1510;
int f[N][3];
int h[N],e[N],ne[N],idx;
int w[N];
int n;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool st[N];//是否有父节点

/*
    f[i][0] 父节点有哨兵
    f[i][1] 子节点有哨兵  的最小花费 不知道哪个子节点
    f[i][2] 自己有哨兵   

    状态表示
    f[i][0] = sum(min(f[j][1],f[j][2]))
    f[i][2] = sum(min(f[j][0],f[j][1],f[j][2])) +w[u];

    f[i][1] = min()
*/
void dfs(int u)
{
    // f[u][0]=0;
    f[u][2] =w[u];
    f[u][1] = 1e9;

    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        dfs(j);

        f[u][0] += min(f[j][1],f[j][2]);
        f[u][2] +=min(f[j][1],min(f[j][0],f[j][2]));
    }
    //由于f[u][0]储存的就是所有的u的字节点的最小值和
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        f[u][1] = min(f[u][1],f[u][0]+f[j][2]-min(f[j][1],f[j][2]));   //要减去自己的值 才是other的值
    }
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a,tw,m;//节点编号 价值 子节点数
        cin>>a>>tw>>m;
        w[a]=tw;
        for(int j=1;j<=m;j++)
        {
            int b;
            cin>>b;
            add(a,b);
            st[b]=1;
        }
    }
    int root =1;
    while(st[root]) root++;
    dfs(root);

    cout<<(min(f[root][1],f[root][2]))<<endl;    
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1510;
int e[N],ne[N],h[N],idx;

int n;
bool st[N];//用来寻找根节点
int f[N][2];//表示以i为根节点 0表示不取这个根 1表示取这个根
/*
    状态计算
    f[i][0] = sum(f[sk][1])
    f[i][1] = sum(min(f[sk][1],f[sk][0]))


*/
void add(int a,int b)
{
    e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void dfs(int u)
{
    f[u][0]=0;
    f[u][1]=1;//如果放士兵 就等于1
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        dfs(j);
        f[u][1]+=min(f[j][0],f[j][1]);
        f[u][0]+=f[j][1];
    }
}
int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);

    while(scanf("%d",&n)!=-1)
    {
        memset(h,-1,sizeof h);
        memset(st,0,sizeof st);
        // memset(f,0,sizeof f);
        idx =0;
        for(int i=1;i<=n;i++)
        {
            // string ch;
            // cin>>ch;
            int a ;
            int son_num ;
            scanf("%d:(%d)",&a,&son_num);
            while(son_num--)
            {
                int b;
                // cin>>b;
                scanf("%d",&b);
                add(a,b);
                st[b]=1;//表示这个点有根节点了
            }
        }

        int root = 0;
        while(st[root]) root++;
        dfs(root);
        // cout<<min(f[root][0],f[root][1])<<endl;
        printf("%d\n",min(f[root][0],f[root][1]));
    }


    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int h[N],e[2*N],w[2*N],ne[2*N],idx;
int n,m;
int f[N][N];
/*
    状态表示：
        f[i][m][j] 表示以i为根节点，在前n个树枝中 树枝数量等于 j的最大的苹果数
    状态计算：
        f[i][m][j] = max(f[i][m][j],f[i][m-1][j],w[i]+f[i][m-1][j-k-1]+f[son][m-1][k])

*/
void add(int a,int b,int c)
{
    w[idx]=c;e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void dfs(int u,int father)
{
    for(int i=h[u];~i;i=ne[i])
    {
        if(e[i]==father) continue;//不能是父节点
        //开始分组dp
        dfs(e[i],u);
        for(int j=m;j>=0;j--)
        {
            for(int k=0;k<=j-1;k++)
            {
                f[u][j] = max(f[u][j],w[i]+f[u][j-k-1]+f[e[i]][k]);//注意此时u上面有一个父节点
            }
        }

    }

}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }

    dfs(1,-1);

    cout<<f[1][m]<<endl;

    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 50010;
int e[N],h[N],ne[N],idx;
int d1[N],d2[N],res;
void add(int a,int b)
{
    e[idx] = b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int sum[N];
int n;
void dfs(int u)
{
    if(d1[u]) return ;//已经计算过了就不算了

    for(int i=h[u]; ~i ; i=ne[i])
    {
        int j= e[i];
        dfs(j);//求j的深度

        if(d1[j]+1>=d1[u])
        {
            d2[u]=d1[u];
            d1[u]= d1[j]+1;
        }
        else if(d1[j]+1>d2[u]) d2[u]=d1[j]+1;
    }
    res = max(res,d1[u]+d2[u]);
}

int main()
{
    memset(h,-1,sizeof h);

    //求和 埃筛法
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=2;j<=n/i;j++)
        {
            sum[i*j]+=i;
        }
    //建立树模型
    for(int i=2;i<=n;i++)
    {
        if(sum[i]<i)
        add(sum[i],i);
    }
    for(int i=1;i<=n;i++) dfs(i);
    // dfs(1);
    // for(int i=1;i<=n;i++)
    // {
    //     res = max(res,d1[i]+d2[i]);
    // }

    cout<<res<<endl;

    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int e[2*N],ne[2*N],h[N],w[2*N],idx;
const int INF = 1e9;
int n;
int p1[N],d1[N];//向下第一长的父节点 以及向下第一长的距离 
int p2[N],d2[N];
int up[N];//某点向上的最长距离

void add(int a,int b,int c)
{
    w[idx]=c;e[idx] = b;ne[idx]=h[a];h[a]=idx++;
}

int dfs_down(int u,int father)//某点的最长向下路径
{
    d1[u]=d2[u]=-INF;
    for(int i=h[u];~i;i=ne[i])
    {
        //开始深搜
        int j=e[i];//它的相邻节点
        if(j==father) continue;
        int dist = dfs_down(j,u)+w[i];//求这个距离是多少
        if(dist>d1[u])//更新最大最小距离
        {
            d2[u]=d1[u];d1[u]=dist;
            p2[u]=p1[u];p1[u]=j;
        }
        else if(dist>d2[u])
        {
            d2[u]=dist;
            p2[u]=j;
        }
    }

    if(d1[u]==-INF) d1[u]=d2[u]=0;
    return d1[u];//返回最大值
}

/*
    如果是father！=u
    up[u] = max(d1[father]+w[u],up[father])
    否则
    up[u] = max(d2[father]+w[u],up[father]);
*/
void dfs_up(int u,int father)//向上的最大距离
{
    // up[u] = -INF;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j==father) continue;
        if(j==p1[u])
        {
            up[j]=max(up[u],d2[u])+w[i];
        }
        else
        {
            up[j]=max(up[u],d1[u])+w[i];
        }

        dfs_up(j,u);
    }
    // return 
}
int main()
{
    memset(h,-1,sizeof h);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }

    dfs_down(1,-1);
    dfs_up(1,-1);

    int res=INF;
    for(int i=1;i<=n;i++) res = min(res,max(up[i],d1[i]));
    cout<<res<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int h[N],w[2*N],e[2*N],ne[2*N],idx;
int ans;
void add(int a,int b,int c)
{
    w[idx]=c, e[idx] = b, ne[idx]=h[a], h[a]=idx++;
}
int dfs(int u,int father)
{
    int dist = 0;
    int d1=0,d2=0;
    for(int i=h[u];~i;i=ne[i])
    {
        //深度搜索寻找最大
        int j = e[i];
        if(father==j) continue;//不能经过自己
        int d = dfs(j,u)+w[i];
        dist = max(dist,d);//一直储存最大的

        if(d>=d1) d2=d1,d1=d;
        else if(d>d2) d2=d;
    }

    ans = max(ans,d1+d2);
    return dist;//返回最大的
}
int main()
{
    memset(h,-1,sizeof h);
    int n;
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }

    dfs(1,-1);
    cout<<ans<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

int n,m=8;
const int N = 16;
int s[N][N];
double f[N][N][N][N][N];
double Xb;

double get(int x1,int y1,int x2,int y2)//求矩阵的和减均值的平方
{
    double t = s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]-Xb;
    return t*t;
}

double dp(int k,int x1,int y1,int x2,int y2)
{
    if(f[k][x1][y1][x2][y2]>=0) return f[k][x1][y1][x2][y2];
    if(k==n) return f[k][x1][y1][x2][y2] = get(x1,y1,x2,y2);

    double t = 1e9;//初始化无穷大

    for(int i=x1;i<x2;i++)//横着切
    {
        t = min(t,dp(k+1,x1,y1,i,y2)+get(i+1,y1,x2,y2));
        t = min(t,dp(k+1,i+1,y1,x2,y2)+get(x1,y1,i,y2));//
    }

    for(int i=y1;i<y2;i++)
    {
        t = min(t,dp(k+1,x1,y1,x2,i)+get(x1,i+1,x2,y2));
        t = min(t,dp(k+1,x1,i+1,x2,y2)+get(x1,y1,x2,i));
    }

    return f[k][x1][y1][x2][y2]=t;
}
int main()
{
    cin>>n;//划分为几个
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>s[i][j];
        }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
        {
              s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];//二维前缀和
        }


    memset(f,-1,sizeof f);//初始化为-1
    Xb = (double)s[m][m]/n;
    printf("%.3lf\n",sqrt(dp(1,1,1,m,m)/n));
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 35;

int n,w[N];
int f[N][N],g[N][N];
//g[l][r] 储存的事l到r的根节点下标
void dfs(int l,int r)
{
    if(l>r) return ;

    int mid  = g[l][r];
    cout<<mid<<' ';
    dfs(l,mid-1);
    dfs(mid+1,r);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i];

    for(int len = 1;len<=n;len++)
    {
        for(int l=1;l+len-1<=n;l++)
        {
            //如果长度为1
            int r= l+len-1;
            if(len==1)
            {
                f[l][r] = w[l];
                g[l][r] = l;
            }
            else
            {
                for(int k=l;k<=r;k++)
                {
                    int left =k==l?1:f[l][k-1];
                    int right = k==r?1:f[k+1][r];

                    int score = w[k] + left*right;
                    if(f[l][r]<score)
                    {
                        f[l][r] = score;
                        g[l][r] = k;
                    }
                }
            }
        }
    }

    cout<<f[1][n]<<endl;
    dfs(1,n);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 55;
int n;
int w[N];
vector<int> f[N][N];

bool cmp(vector<int> &a,vector<int> &b)
{
    if(a.size()!=b.size()) return a.size()<b.size();
    for(int i=a.size()-1;i>=0;i--)
    {
        if(a[i]!=b[i]) return a[i]<b[i];
    }
    return true;
}

vector<int> add(vector<int> a,vector<int> b)
{
    vector<int> c;
    int t = 0;
    for(int i=0;i<a.size()||i<b.size();i++)
    {
        if(i<a.size()) t+=a[i];
        if(i<b.size()) t+=b[i];
        c.push_back(t%10);
        t/=10;
    }
    while(t) c.push_back(t%10),t/=10;
    return c;
}

vector<int> mul(vector<int> a,LL b)
{
    vector<int> c;
    LL t = 0;
    for(int i=0;i<a.size();i++)
    {
        t+=b*a[i];
        c.push_back(t%10);
        t/=10;
    }
    while(t) c.push_back(t%10),t/=10;
    return c;

}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
    }

    for(int len = 3;len<=n;len++)
    {
        for(int l=1,r;(r=l+len-1)<=n;l++)
        {
            for(int k=l+1;k<r;k++)
            {
                vector<int> new_val = mul(mul({w[l]},w[k]),w[r]);
                new_val = add(add(new_val,f[l][k]),f[k][r]);

                if(f[l][r].empty()||cmp(new_val,f[l][r])) f[l][r] = new_val;
            }
        }
    }

    auto res = f[1][n];
    for(int i=res.size()-1;i>=0;i--) cout<<res[i];


    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 210;//循环要变成两倍

int f[N][N];
int n,w[N];
/*
    状态表示：合并为矩阵(l,r)时，所需的最大能量数
    状态方程：f[l][r] = max(f[i][j],f[l][k]+f[k][r]+w[l]*w[k]*w[r];
*/
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
        w[i+n] = w[i];
    }

    // memset(f,-0x3f,sizeof f);

    for(int len=3;len<=n+1;len++)
    {
        for(int l=1;l+len-1<=2*n;l++)
        {
            int r = l+len-1;
            for(int k=l+1;k<r;k++)
            {
                f[l][r] = max(f[l][r],f[l][k]+f[k][r]+w[l]*w[k]*w[r]);
            }
        }
    }
    int res = 0;
    for(int i=1;i<=n;i++) res = max(res,f[i][i+n]);
    cout<<res<<endl;
    return 0;
}