Giải bài trực tuyến

Bạn ninja Rantaro đang chăm chỉ luyện khinh công. Một ngày, Rantaro cắm các cọc tre từ bờ bên trái sang bờ bên phải của một con sông và luyện tập như sau: Rantaro sẽ nhảy lên cọc đầu tiên bên trái, nhảy qua một số cọc tre về phía bên phải trước khi nhảy lên cọc cuối cùng và sang bờ bên kia. Rantaro luôn nhảy hướng về đích chứ không bao giờ nhảy lùi, đồng thời, một số cọc có thể bị nhảy qua, nhưng Rantaro luôn nhảy lên cọc đầu tiên và cuối cùng.

Giả sử độ cao hiện tại của các cọc tre lần lượt là H₁, H₂, …, H_n từ trái qua phải. Ở mỗi bước, Rantaro có thể lựa chọn:

• Nhảy cao đến cọc kế tiếp và mất x năng lượng cho mỗi đơn vị độ cao. Nói cách khác, Rantaro có thể nhảy từ cọc i sang cọc i+1 và mất max(H_i+1 - H_i, 0) * x năng lượng.
• Nhảy xa đến một cọc khác nếu cọc đó và tất cả các cọc ở giữa đều thấp hơn cọc đang đứng. Mỗi đơn vị độ dài sẽ làm cho Rantaro mất y năng lượng. Nói cách khác, Rantaro có thể nhảy từ cọc i sang cọc j nếu H_i+1, H_i+2, …, H_j < H_i và mất (j - i) * y năng lượng.

Mỗi khi Rantaro nhảy lên một cọc tre, cọc tre sẽ bị lún và độ cao của cọc đó sẽ giảm đi 1 trước khi Rantaro thực hiện bước nhảy tiếp theo. Ví dụ, nếu có 2 cọc tre với độ cao là (3, 5). Rantaro sẽ nhảy lên cọc đầu tiên và làm độ cao của cọc đó giảm xuống 2. Khi Rantaro nhảy lên cọc cuối sẽ mất (5 - 2) * x năng lượng. Sau khi sang bờ bên kia, độ cao của 2 cọc sẽ là (2, 4). Trong bài này, chúng ta bỏ qua năng lượng để nhảy từ bờ lên cọc đầu tiên và từ cọc cuối cùng xuống bờ bên kia.

Sau khi sang bờ bên phải, Rantaro lại nhảy lại về bờ bên trái theo cách tương tự. Tuy nhiên, Rantaro sẽ mất u năng lượng cho mỗi đơn vị độ cao và v năng lượng cho mỗi đơn vị độ dài. Bạn cần giúp Rantaro tính tổng số năng lượng ít nhất cần dùng cho cả hai lượt nhảy.

Ví dụ, nếu x = 2, y = 1, u = 5, v = 50, độ cao các cọc là (9, 2, 6, 2, 4). Ở lần nhảy từ trái qua phải, Rantaro có thể chỉ mất 4 năng lượng nếu nhảy từ cọc 1 đến cọc 5. Sau khi sang bờ bên phải, độ cao các cọc lần lượt là (8, 2, 6, 2, 3). Ở lần nhảy về, Rantaro sẽ nhảy 5 → 4 → 3 → 2 → 1 và mất ((6-1) + (8-1)) * 5 = 60 năng lượng. Tổng cộng Rantaro sẽ mất 64 năng lượng. Nếu ở lần nhảy từ trái qua phải, Rantaro nhảy 1 → 3 → 5 sẽ mất 4 năng lượng và độ cao các cọc sau khi nhảy là (8, 2, 5, 2, 3). Ở lần nhảy về, Rantaro sẽ chỉ mất 55 năng lượng và tổng cộng sẽ là 59 năng lượng.

Dữ liệu

• Dòng đầu ghi số N.
• Dòng sau ghi 4 số nguyên x, y, u, v.
• Dòng tiếp theo ghi N số nguyên thể hiện độ cao ban đầu của các cọc tre.

Kết quả

• Một số duy nhất thể hiện tổng số năng lượng ít nhất mà Rantaro phải dùng.

Lưu ý

• Các giá trị của H ở công thức nhảy cao và nhảy xa thể hiện độ cao ở thời điểm nhảy, không phải độ cao ban đầu.
• Ở lần nhảy về, hướng nhảy thay đổi và bạn không thể áp dụng y nguyên công thức của lần nhảy đi (ví dụ, bạn có thể đánh lại chỉ số các cọc từ phải qua trái trước khi áp dụng công thức nhảy cao và nhảy xa).
• Trong thời gian thi, bài nộp của bạn sẽ được chấm với cả 4 ví dụ bên dưới.

Giới hạn

• 2 ≤ N, H_i ≤ 100; 1 ≤ x, y, u, v ≤ 100.
• 50% số test có N ≤ 20.
• 70% số test có N ≤ 40.

Ví dụ

Dữ liệu 1:
5
2 1 5 50
9 2 6 2 4

Kết quả 1:
59
Cách nhảy: 1 → 3 → 5, 5 → 4 → 3 → 2 → 1

Dữ liệu 2:
2
5 1 3 1
11 11

Kết quả 2:
8
Cách nhảy: 1 → 2, 2 → 1

Dữ liệu 3:
7
1 1 100 1
7 2 2 2 2 2 4

Kết quả 3:
612
Cách nhảy: 1 → 2 → 3 → 4 → 5 → 6 → 7, 7 → 2 → 1

Dữ liệu 4:
6
5 1 20 1
9 5 2 7 2 5

Kết quả 4:
207
Cách nhảy: 1 → 6, 6 → 5 → 4 → 2 → 1

Dữ liệu 2:
11 11
Cách nhảy: 1 -> 6, 6 -> 5 -> 4 -> 2 ->