#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+1;
int n,a,b,c,s[N];
int f[N],q[N];

int read() {
    int x=0; bool f=true; char ch=0;
    while (!isdigit(ch) ) f&=(ch!='-'),ch=getchar();
    while (isdigit(ch) ) x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
    return f?x:-x;
}
int get(int x) {
    return f[x]+a*s[x]*s[x]-b*s[x];
}
double slope(int x,int y) {
    int X=get(x)-get(y),Y=s[x]-s[y];
    return !X?1e30:X*1.0/Y;
}
signed main()
{
    n=read(),a=read(),b=read(),c=read();
    for (int i=1;i<=n;i++) s[i]=s[i-1]+read();
    int hh=0,tt=0; for (int i=1;i<=n;i++)
    {
        while (hh<tt&&slope(q[hh+1],q[hh])>2*a*s[i]) hh++;
        int p=q[hh],sum=s[i]-s[p]; f[i]=f[p]+a*sum*sum+b*sum+c;
        while (hh<tt&&slope(i,q[tt])>slope(q[tt],q[tt-1]) ) tt--;
        q[++tt]=i;
    }
    printf("%lld",f[n]);
    return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+1;
int d[N],a[N],s[N];
int f[2][N],q[N];
int n,m,p;

int read() {
    int x=0; char ch=0; while (!isdigit(ch) ) ch=getchar();
    while (isdigit(ch) ) x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
    return x;
}
double slope(int i,int x,int y) {
    return 1.0*(f[i][x]+s[x]-f[i][y]-s[y])/(x-y);
}
signed main()
{
    n=read(),m=read(),p=read();
    for (int i=2;i<=n;i++) d[i]=d[i-1]+read();
    for (int i=1,h;i<=m;i++) h=read(),a[i]=read()-d[h];
    sort(a+1,a+m+1); for (int i=1;i<=m;i++) s[i]=s[i-1]+a[i];
    memset(f,0x3f,sizeof f); f[0][0]=f[1][0]=0;

    for (int i=1;i<=p;i++)
    {
        int hh=0,tt=0,pre=i-1&1;
        for (int j=1;j<=m;j++)
        {
            while (hh<tt&&slope(pre,q[hh+1],q[hh])<a[j]) hh++;
            int p=q[hh]; f[i&1][j]=f[pre][p]+a[j]*(j-p)-s[j]+s[p];
            while (hh<tt&&slope(pre,j,q[tt])<slope(pre,q[tt],q[tt-1]) ) tt--;
            q[++tt]=j;
        }
    }
    printf("%lld",f[p&1][m]);
    return 0;
}

#include<bits/stdc++.h>
#define int long long
#define front q[hh]
#define back q[tt]
using namespace std;
const int N=5e5+1;
int n,S,t[N],c[N];
int f[N],q[N];

int read() {
    int x=0; char ch=0; bool f=true;
    while (!isdigit(ch) ) f&=(ch!='-'),ch=getchar();
    while (isdigit(ch) ) x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
    return f?x:-x;
}
double slope(int x,int y) { //斜率
    int X=f[x]-f[y],Y=c[x]-c[y];
    if (!X) return (Y>0)?1e30:-1e30;
    return X*1.0/Y;
}
signed main()
{
    n=read(),S=read(); for (int i=1;i<=n;i++)
    t[i]=t[i-1]+read(),c[i]=c[i-1]+read();
    int hh=0,tt=0; for (int i=1;i<=n;i++)
    {
        int l=hh,r=tt; while (l<r) { int mid=(l+r)>>1;
        slope(q[mid+1],q[mid])>S+t[i]?r=mid:l=mid+1; }
        int p=q[r]; f[i]=f[p]+t[i]*(c[i]-c[p])+S*(c[n]-c[p]);
        while (hh<tt&&slope(i,q[tt])<slope(q[tt],q[tt-1]) ) tt--;
        q[++tt]=i;
    }
    printf("%lld",f[n]);
    return 0;
}

#include<bits/stdc++.h>
#define int long long
#define front q[hh]
#define back q[tt]
using namespace std;
const int N=3e5+1;
int n,S,t[N],c[N];
int f[N],q[N];

int read() {
    int x=0; char ch=0; while (!isdigit(ch) ) ch=getchar();
    while (isdigit(ch) ) x=(x<<3)+(x<<1)+(ch&15),ch=getchar(); return x;
}
double slope(int x,int y) { //斜率
    int X=f[x]-f[y],Y=c[x]-c[y];
    if (!X) return (Y>0)?1e30:-1e30;
    return X*1.0/Y;
}
signed main()
{
    n=read(),S=read(); for (int i=1;i<=n;i++)
    t[i]=t[i-1]+read(),c[i]=c[i-1]+read();
    int hh=0,tt=0; for (int i=1;i<=n;i++)
    {
        while (hh<tt&&slope(q[hh+1],q[hh])<S+t[i]) hh++;
        int p=q[hh]; f[i]=f[p]+t[i]*(c[i]-c[p])+S*(c[n]-c[p]);
        while (hh<tt&&slope(i,q[tt])<slope(q[tt],q[tt-1]) ) tt--;
        q[++tt]=i;
    }
    printf("%lld",f[n]);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=5001;
int n,s,t[N],c[N];
long long f[N];

int read()
{
    int x=0; char ch=0; while (!isdigit(ch) ) ch=getchar();
    while (isdigit(ch) ) x=(x<<3)+(x<<1)+(ch&15),ch=getchar(); return x;
}
int main()
{
    n=read(),s=read(); for (int i=1;i<=n;i++)
    t[i]=t[i-1]+read(),c[i]=c[i-1]+read();
    memset(f,0x3f,sizeof f); f[0]=0;
    for (int i=1;i<=n;i++)
        for (int j=0;j<i;j++)
            f[i]=min(f[i],f[j]+1ll*(c[i]-c[j])*t[i]+1ll*s*(c[n]-c[j]) );
    printf("%lld",f[n]);
    return 0;
}

#include<bits/stdc++.h>
#define ll long long
#define mid (l+r>>1)
#define ls T[rt].l
#define rs T[rt].r
using namespace std;
const int N=4e5;
vector<int> num;
int root[N<<2];
int n,m,rp;

struct Q {
    int op,l,r;
    ll x;
}a[N];

struct SGT
{
    int tot;
    struct node {
        int l,r,tag;
        ll cnt;
    }T[N<<7];

    void push_down(int rt,int l,int r)
    {
        int tag=T[rt].tag; T[rt].tag=0;
        if (!ls) ls=++tot; if (!rs) rs=++tot;
        T[ls].tag+=tag,T[ls].cnt+=1ll*tag*(mid-l+1);
        T[rs].tag+=tag,T[rs].cnt+=1ll*tag*(r-mid);
    }
    void modify(int &rt,int l,int r,int L,int R)
    {
        if (!rt) rt=++tot; if (L<=l&&r<=R) return
        T[rt].tag++,T[rt].cnt+=r-l+1,void();

        push_down(rt,l,r);
        if (L<=mid) modify(ls,l,mid,L,R);
        if (mid<R) modify(rs,mid+1,r,L,R);
        T[rt].cnt=T[ls].cnt+T[rs].cnt;
    }
    ll query(int rt,int l,int r,int L,int R)
    {
        if (L<=l&&r<=R) return T[rt].cnt;

        push_down(rt,l,r);
        if (R<=mid) return query(ls,l,mid,L,R);
        if (mid<L) return query(rs,mid+1,r,L,R);
        return query(ls,l,mid,L,R)+query(rs,mid+1,r,L,R);
    }
}A;

void update(int rt,int l,int r,int L,int R,int p) {
    A.modify(root[rt],1,n,L,R); if (l==r) return;
    p<=mid?update(rt<<1,l,mid,L,R,p):update(rt<<1|1,mid+1,r,L,R,p);
}
int Query(int rt,int l,int r,int L,int R,ll k) {
    if (l==r) return l; ll cnt=A.query(root[rt<<1|1],1,n,L,R);
    return k>cnt?Query(rt<<1,l,mid,L,R,k-cnt):Query(rt<<1|1,mid+1,r,L,R,k);
}
int Hash(int x) {
    return lower_bound(num.begin(),num.end(),x)-num.begin();
}
int main()
{
    scanf("%d%d",&n,&m); for (int i=0;i<m;i++)
    scanf("%d%d%d%lld",&a[i].op,&a[i].l,&a[i].r,&a[i].x);
    for (int i=0;i<m;i++) if (a[i].op==1) num.push_back(a[i].x);
    sort(num.begin(),num.end() ),num.erase(unique(num.begin(),num.end() ),num.end() );

    for (int i=0;i<m;i++)
    {
        int op=a[i].op,l=a[i].l,r=a[i].r;
        if (op==1) update(1,0,num.size()-1,l,r,Hash(a[i].x) );
        else printf("%d\n",num[Query(1,0,num.size()-1,l,r,a[i].x)]);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int n,m,ans,dis[N],a[N],q[N];
int tim,dfn[N],low[N],fa[N];
vector<int> g[N];

void cycle(int x,int y)
{
    int cnt=0,hh=0,tt=-1;
    for (int u=y;u^x;u=fa[u]) a[++cnt]=dis[u]; a[++cnt]=dis[x];
    for (int i=1;i<=cnt;i++) a[cnt+i]=a[i]; reverse(a+1,a+2*cnt+1);

    for (int i=1;i<=cnt<<1;i++)
    {
        while (hh<=tt&&i-q[hh]>cnt/2) hh++;
        if (hh<=tt) ans=max(ans,a[i]+a[q[hh] ]+i-q[hh]);
        while (hh<=tt&&a[q[tt] ]-q[tt]<a[i]-i) tt--;
        q[++tt]=i;
    }
    for (int i=2;i<=cnt;i++)
        dis[x]=max(dis[x],a[i]+min(i-1,cnt-i+1) );
}
void tarjan(int u,int f)
{
    dfn[u]=low[u]=++tim;
    for (int v:g[u]) if (v^f)
    {
        if (!dfn[v])
        {
            fa[v]=u; tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if (dfn[u]<low[v]) {
                ans=max(ans,dis[u]+1+dis[v]);
                dis[u]=max(dis[u],dis[v]+1);
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
    for (int v:g[u])
        if (dfn[u]<dfn[v]&&fa[v]^u)
            cycle(u,v);
}
int main()
{
    scanf("%d%d",&n,&m);

    while (m--)
    {
        int k,x,y;
        scanf("%d%d",&k,&x);

        while (--k)
        {
            scanf("%d",&y);
            g[x].push_back(y);
            g[y].push_back(x);
            x=y;
        }
    }
    tarjan(1,0);
    printf("%d",ans);
    return 0;
}

#include<bits/stdc++.h>
#define P pair<int,int>
#define v e.first
#define w e.second
using namespace std;
const int N=2e4+1; int m,q,cnt;
int n,f[N][15],depth[N],dis[N],csum[N];
int tim,dfn[N],low[N],fa[N],a[N],s[N];
vector<P> G[N],g[N];

void build_cycle(int x,int y,int z)
{
    int sum=z; for (int u=y;u^x;u=fa[u])
    s[u]=sum,sum+=a[u]; s[x]=csum[x]=sum;
    cnt++; g[x].push_back( {cnt,0} );
    for (int u=y;u^x;u=fa[u]) csum[u]=sum,
    g[cnt].push_back( {u,min(s[u],sum-s[u]) } );
}
void tarjan(int u,int father)
{
    dfn[u]=low[u]=++tim;
    for (auto e:G[u]) if (v^father)
    {
        if (!dfn[v])
        {
            fa[v]=u,a[v]=w;
            tarjan(v,u); low[u]=min(low[u],low[v]);
            if (dfn[u]<low[v]) g[u].push_back( {v,w} );
        }
        else low[u]=min(low[u],dfn[v]);
    }
    for (auto e:G[u])
        if (dfn[u]<dfn[v]&&fa[v]^u)
            build_cycle(u,v,w);
}
void dfs(int u,int Fa) { depth[u]=depth[Fa]+1,f[u][0]=Fa;
    for (int i=1;i<15;i++) f[u][i]=f[f[u][i-1] ][i-1];
    for (auto e:g[u]) dis[v]=dis[u]+w,dfs(v,u);
}
int LCA(int x,int y,int &X,int &Y)
{
    if (depth[x]>depth[y]) swap(x,y); for (int i=14;i>=0;i--)
    if (depth[x]<=depth[f[y][i] ]) y=f[y][i]; if (x==y) return x;
    for (int i=14;i>=0;i--) if (f[x][i]^f[y][i]) x=f[x][i],y=f[y][i];
    X=x,Y=y; return f[x][0];
}
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    cnt=n;

    while (m--) { int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        G[x].push_back( {y,z} );
        G[y].push_back( {x,z} );
    }tarjan(1,0),dfs(1,0);

    while (q--)
    {
        int x,y,z,X,Y; scanf("%d%d",&x,&y); z=LCA(x,y,X,Y);
        if (z<=n) printf("%d\n",dis[x]+dis[y]-2*dis[z]);
        else { int dx=dis[x]-dis[X],dy=dis[y]-dis[Y],t=abs(s[X]-s[Y]);
        printf("%d\n",dx+dy+min(t,csum[X]-t) ); }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int n,m,ans,dis[N],a[N],q[N];
int tim,dfn[N],low[N],fa[N];
vector<int> g[N];

void cycle(int x,int y)
{
    int cnt=0,hh=0,tt=-1;
    for (int u=y;u^x;u=fa[u]) a[++cnt]=dis[u]; a[++cnt]=dis[x];
    for (int i=1;i<=cnt;i++) a[cnt+i]=a[i]; reverse(a+1,a+2*cnt+1);

    for (int i=1;i<=cnt<<1;i++)
    {
        while (hh<=tt&&i-q[hh]>cnt/2) hh++;
        if (hh<=tt) ans=max(ans,a[i]+a[q[hh] ]+i-q[hh]);
        while (hh<=tt&&a[q[tt] ]-q[tt]<a[i]-i) tt--;
        q[++tt]=i;
    }
    for (int i=2;i<=cnt;i++)
        dis[x]=max(dis[x],a[i]+min(i-1,cnt-i+1) );
}
void tarjan(int u,int f)
{
    dfn[u]=low[u]=++tim;
    for (int v:g[u]) if (v^f)
    {
        if (!dfn[v])
        {
            fa[v]=u; tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if (dfn[u]<low[v]) {
                ans=max(ans,dis[u]+1+dis[v]);
                dis[u]=max(dis[u],dis[v]+1);
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
    for (int v:g[u])
        if (dfn[u]<dfn[v]&&fa[v]^u)
            cycle(u,v);
}
int main()
{
    scanf("%d%d",&n,&m);

    while (m--)
    {
        int k,x,y;
        scanf("%d%d",&k,&x);

        while (--k)
        {
            scanf("%d",&y);
            g[x].push_back(y);
            g[y].push_back(x);
            x=y;
        }
    }
    tarjan(1,0);
    printf("%d",ans);
    return 0;
}