Xâm lược quái vật

Một trò chơi bắn quái có $n$ màn chơi được xếp thành một dãy, đánh số từ $1$ đến $n$. Màn thứ $i$ chứa $a_i$ quái thường (mỗi con có $1$ máu) và đúng $1$ trùm (có $2$ máu).

Người chơi có ba khẩu súng:

• Súng lục: gây $1$ sát thương lên một mục tiêu trong màn hiện tại, thời gian nạp đạn $r_1$.
• Súng laser: gây $1$ sát thương lên tất cả mục tiêu trong màn hiện tại (kể cả trùm), thời gian nạp đạn $r_2$.
• Súng bắn tỉa: hạ gục ngay lập tức một mục tiêu bất kỳ, thời gian nạp đạn $r_3$.

Ban đầu cả ba khẩu súng đều chưa có đạn, và tại mỗi thời điểm người chơi chỉ nạp được một khẩu. Bắn một khẩu đã nạp đạn không tốn thời gian, đạn là vô hạn; vì vậy chi phí của mỗi phát bắn đúng bằng thời gian nạp đạn của khẩu súng đó.

Hai quy tắc quan trọng của trò chơi:

• Người chơi không được dùng súng lục hoặc súng bắn tỉa nhắm vào trùm của màn $i$ khi $a_i$ con quái thường của màn đó chưa bị tiêu diệt hết. Súng laser không bị hạn chế này.
• Nếu người chơi gây sát thương lên trùm nhưng không hạ gục ngay (trùm còn $1$ máu), người chơi bị buộc phải rời sang một màn kề với màn hiện tại.

Hai màn được gọi là kề nhau nếu chỉ số của chúng chênh nhau đúng $1$. Người chơi có thể tự ý di chuyển sang màn kề bất cứ lúc nào; mỗi lần di chuyển tốn $d$ thời gian và trong lúc di chuyển không được nạp đạn hay bắn.

Người chơi bắt đầu ở màn $1$. Trò chơi kết thúc ngay khi trùm của mọi màn đều đã bị tiêu diệt, không bắt buộc phải dừng ở màn $n$.

Hãy tính thời gian nhỏ nhất để hoàn thành trò chơi.

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 là thời gian nhỏ nhất để tiêu diệt hết tất cả các 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ụ