Xe thám hiểm hành tinh Tycho VIII cần trở về căn cứ sau khi thu thập các mẫu khoáng sản. Tycho di chuyển theo một đường thẳng từ vị trí \(0\) đến căn cứ ở vị trí \(b\). Khi di chuyển, xe tiến chậm nhưng đều với tốc độ \(1\) đơn vị mỗi giây. Mỗi giây, Tycho chịu \(1\) đơn vị tổn hại do điều kiện môi trường khắc nghiệt trên hành tinh.

Tình hình còn tệ hơn bởi bức xạ từ một sao xung gần đó: cứ mỗi \(p\) giây, bức xạ lại gây thêm \(d\) đơn vị tổn hại. Tuy nhiên, xe có thể tránh tổn hại do bức xạ bằng cách trú tại một trong \(n\) chỗ trú ẩn dọc đường, chẳng hạn như hang động, thảm thực vật, những tảng đá lớn hoặc xác các loài động vật khổng lồ trên hành tinh. Tycho có thể chọn đứng yên ở bất kỳ vị trí nào trong một số nguyên giây tùy ý.

Vị trí xuất phát \(0\) và căn cứ tại \(b\) đều có che chắn, nên Tycho không chịu tổn hại do bức xạ khi ở đó.

Tổng mức tổn hại nhỏ nhất mà Tycho phải chịu trên đường trở về căn cứ là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa bốn số nguyên \(b\), \(p\), \(d\), \(n\) cách nhau bằng một dấu cách: vị trí căn cứ, chu kỳ phát xung của sao xung, mức tổn hại bổ sung do bức xạ của mỗi lần phát xung và số chỗ trú ẩn.

\(n\) dòng tiếp theo, mỗi dòng chứa một số nguyên, lần lượt là các vị trí trú ẩn \(a_1,\ldots,a_n\), thỏa mãn \(0<a_1<\cdots<a_n<b\).

Dữ liệu ra

In một số nguyên duy nhất: tổng mức tổn hại nhỏ nhất mà Tycho phải chịu để đến được vị trí \(b\).

Ràng buộc

• \(1\le b\le 10^{12}\).
• \(1\le p<b\).
• \(0\le d\le 10^6\).
• \(0\le n\le 10^5\) và \(n<b\).
• Các vị trí trú ẩn là số nguyên và thỏa mãn \(0<a_1<\cdots<a_n<b\).

Phân nhóm

Các bộ kiểm thử được chia thành các nhóm, mỗi nhóm có một số điểm. Để nhận được điểm của một nhóm, chương trình phải giải đúng tất cả các bộ kiểm thử trong nhóm đó. Điểm cuối cùng là điểm cao nhất của một lần nộp bài.

1. \(8\) điểm: \(p\le 10^6\) và Tycho không cần chờ sau khi rời vị trí \(0\) để đạt tổng mức tổn hại nhỏ nhất. Tycho vẫn có thể cần chờ tại vị trí \(0\) trước khi bắt đầu di chuyển. Chẳng hạn, các ví dụ 2, 3 và 4 thuộc nhóm này.
2. \(5\) điểm: \(b\le 1000\), \(p\le 100\) và \(n\le 10\).
3. \(7\) điểm: \(b\le 1000\).
4. \(15\) điểm: \(p\le 10^6\) và \(n\le 1000\).
5. \(20\) điểm: \(p\le 100\).
6. \(35\) điểm: \(p\le 10^6\).
7. \(10\) điểm: không có ràng buộc bổ sung.

Ví dụ

18 4 5 2
8
15

29

18 4 0 2
8
15

18

18 10 100 2
8
15

20

18 4 100 0

418

65 20 100 3
14
25
33

172