Cuộc xâm lăng của quái vật

Bạn chơi một trò bắn quái vật gồm $n$ màn xếp thành một hàng, đánh số từ $1$ đến $n$. Ở màn thứ $i$ có $a_i$ con quái vật thường (mỗi con $1$ máu) và đúng $1$ con trùm (boss) có $2$ máu.

Bạn có ba loại súng, ban đầu cả ba đều chưa nạp đạn và mỗi lần chỉ nạp được đúng một khẩu:

• Súng lục: gây $1$ sát thương lên một con quái vật, thời gian nạp $r_1$.
• Súng laser: gây $1$ sát thương lên tất cả quái vật ở màn hiện tại (bao gồm cả trùm), thời gian nạp $r_2$.
• Súng AWP: tiêu diệt tức thì một con quái vật bất kỳ, thời gian nạp $r_3$.

Bắn (khi súng đã nạp) và ngắm đều tốn $0$ thời gian, bạn có vô hạn đạn. Bạn không được dùng súng lục hoặc AWP để bắn trùm khi ở màn đó vẫn còn quái vật thường chưa bị tiêu diệt.

Nếu bạn gây sát thương lên trùm nhưng không giết được ngay (tức trùm còn $1$ máu sau đòn đánh), bạn buộc phải rời khỏi màn hiện tại sang một màn kề. Ngoài ra bạn cũng có thể chủ động di chuyển sang màn kề bất cứ lúc nào. Màn kề của màn $i$ (với $1<i<n$) là $i-1$ và $i+1$; màn $1$ chỉ kề màn $2$, màn $n$ chỉ kề màn $n-1$. Mỗi lần di chuyển giữa hai màn kề tốn $d$ thời gian, và trong lúc di chuyển bạn không được nạp đạn hay bắn.

Bạn bắt đầu ở màn $1$. Mục tiêu là tiêu diệt trùm ở tất cả các màn. Hãy tính thời gian nhỏ nhất để hoàn thành (không nhất thiết phải kết thúc ở màn $n$, chỉ cần mọi trùm đều bị tiêu diệt).

Dữ liệu vào

• Dòng đầu chứa năm số nguyên $n$, $r_1$, $r_2$, $r_3$, $d$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

Một số nguyên duy nhất: thời gian nhỏ nhất để tiêu diệt hết mọi trùm.

Ràng buộc

• $2\le n\le {10}^6$
• $1\le r_1\le r_2\le r_3\le {10}^9$
• $1\le d\le {10}^9$
• $1\le a_i\le {10}^6$

Ví dụ