import sys readline=sys.stdin.readline class AVL_Node_dict: """ノード Attributes: key (any): ノードのキー。比較可能なものであれば良い。(1, 4)などタプルも可。 val (any): ノードの値。 left (Node): 左の子ノード。 right (Node): 右の子ノード。 bias (int): 平衡度。(左部分木の高さ)-(右部分木の高さ)。 size (int): 自分を根とする部分木の大きさ """ def __init__(self,parent,key,value): self.parent=parent self.key=key self.value=value self.left=None self.right=None self.bias=0 self.size=1 class AVLTree_dict: def __init__(self): self.root=None def Rotate_Left(self,node): node_right=node.right node_right.size=node.size node.size-=1 if node_right.right!=None: node.size-=node_right.right.size if node_right.bias==-1: node_right.bias=0 node.bias=0 else: #assert node_right.bias==0 node_right.bias=1 node.bias=-1 node.right=node_right.left node_right.left=node return node_right def Rotate_Right(self,node): node_left=node.left node_left.size=node.size node.size-=1 if node_left.left!=None: node.size-=node_left.left.size if node_left.bias==1: node_left.bias=0 node.bias=0 else: #assert node_left.bias==0 node_left.bias=-1 node.bias=1 node.left=node_left.right node_left.right=node return node_left def Rotate_Left_Right(self,node): node_left=node.left node_left_right=node_left.right #assert node.bias==2 #assert node_left.bias==-1 #assert node_left_right.bias in (-1,0,1) node_left_right.size=node.size node.size-=node_left.size if node_left_right.right!=None: node.size+=node_left_right.right.size node_left.size-=1 if node_left_right.right!=None: node_left.size-=node_left_right.right.size node_left.right=node_left_right.left node_left_right.left=node_left node.left=node_left_right.right node_left_right.right=node self.Update_Bias_Double(node_left_right) return node_left_right def Rotate_Right_Left(self,node): node_right=node.right node_right_left=node_right.left #assert node.bias==-2 #assert node_right.bias==1 #assert node_right_left.bias in (-1,0,1) node_right_left.size=node.size node.size-=node_right.size if node_right_left.left!=None: node.size+=node_right_left.left.size node_right.size-=1 if node_right_left.left!=None: node_right.size-=node_right_left.left.size node_right.left=node_right_left.right node_right_left.right=node_right node.right=node_right_left.left node_right_left.left=node self.Update_Bias_Double(node_right_left) return node_right_left def Update_Bias_Double(self,node): #assert node.right.bias*node.left.bias==-2 #assert node.right.bias>0 if node.bias==1: node.right.bias=-1 node.left.bias=0 elif node.bias==-1: node.right.bias=0 node.left.bias=1 else: node.right.bias=0 node.left.bias=0 node.bias=0 def __getitem__(self,key): v=self.root while v!=None: if keykey: if retu==None or retu[0]>v.key: retu=(v.key,v.value) v=v.left else: v=v.right return retu def Bisect_Left(self,key): retu=None v=self.root while v!=None: if v.key1: mid=(ok+ng)//2 a0,b0=self.lines.Find_Kth_Element(mid) a1,b1=self.lines.Find_Kth_Element(mid+1) if a0*x+b0>a1*x+b1: ok=mid else: ng=mid a,b=self.lines.Find_Kth_Element(ok+1) return a*x+b def __getitem__(self,a): return self.lines[a] def __setitem__(self,a,b): self.add_line(a,b) N,A,B,W=map(int,readline().split()) D=list(map(int,readline().split())) inf=1<<60 dp=[inf]*N CHT=Convex_Hull_Trick() for i in range(N): dp[i]=W*2-2*A*i+B*i*(i+1)+D[i]*2 if i: dp[i]=min(dp[i],CHT(i)+D[i]*2-2*i*A+B*i**2) CHT.add_line(-B*(2*i+1),dp[i]+2*(i+1)*A+B*i*(i+1)) ans=W-A*N+B*N*(N+1)//2 for i in range(N): ans=min(ans,(dp[i]-2*A*(N-1-i)+B*(N-i)*(N-i-1))//2) print(ans)