Vương quốc Valanro có ~N~ công trình, mỗi công trình có mã số là ~a_i~ (~1 \le i \le N~), vì muốn tối ưu hóa việc quản lý dân cư, quốc vương KaJo quyết định gộp các công trình thành ~M~ đại công trình.

• Một đại công trình sẽ được dựng lên bằng các công trình liền kề nhau (Đại công trình bao gồm tối thiểu một công trình).
• Mã số của đại công trình là ước chung lớn nhất của các mã số của các công trình trong đại công trình đó.

Xây dựng một đại công trình sẽ tốn khá nhiều công sức, vì thế quốc vương đã thỏa thuận với đội thi công như sau:

• Một đại công trình có mã số là ~K~ sẽ tốn chi phí là ~X~ để xây dựng.
• Một đại công trình có mã số khác ~K~ sẽ tốn chi phí là ~Y~ để xây dựng.

Ví dụ: Cho ~5~ công trình có các mã số là ~[8, 4, 6, 10, 14]~ cần dựng lên ~3~ đại công trình với ~K~, ~X~, ~Y~ lần lượt là ~2, 2, 3~. Dựng các đại công trình có mã số là ~[8, 2, 2]~ bằng cách gộp các công trình ~[8]~, ~[4, 6]~, ~[10, 14]~ với chi phí là ~3 + 2 + 2 = 7~.

Hãy giúp quốc vương KaJo tìm cách dựng các đại công trình có chi phí thấp nhất.

Input Format

• Dòng thứ nhất gồm ~2~ số nguyên dương ~N~, ~M~ (~N \le 10^{4}~, ~M \le min(20, N)~).
• Dòng thứ hai gồm ~3~ số nguyên dương ~K~, ~X~, ~Y~ (~K, X, Y \le 10^{9}~).
• Dòng thứ ba gồm ~N~ số nguyên dương ~a_i~ (~a_i \le 10^{9}~).

Output Format

• In ra chi phí thấp nhất để vương quốc thực hiện dự án.

Subtasks

• Có ~20\%~ số lượng test thỏa mãn điều kiện: ~N \le 10~.

• Có ~30\%~ số lượng test khác thỏa mãn điều kiện: ~N \le 2000~.

• Có ~50\%~ số lượng test còn lại thỏa mãn điều kiện: ~N \le 10^{4}~.

Sample Input 1

5 3
2 2 3
8 4 6 10 14

Sample Output 1

7

Sample Input 2

8 4
3 3 4
9 6 12 6 6 9 9 12 

Sample Output 2

13