Một tài xế giao hàng cần vận chuyển một lô hàng từ điểm xuất phát (vị trí 0) đến kho hàng ở vị trí \(h\) trên một con đường. Tuy nhiên, hành trình này không đơn giản vì nhiều yếu tố tác động vào:

• Mỗi giây di chuyển, tài xế làm mất 1 món hàng trong lô hàng do đường xóc, gập ghềnh, hoặc va đập trong quá trình vận chuyển.

• Sau mỗi \(t\) giây, nếu tài xế không dừng lại tại các trạm bảo vệ trên đường, tài xế sẽ bị mất g món hàng do bị đối thủ tranh giành.

• Tài xế có thể dừng lại ở các trạm bảo vệ để bảo vệ hàng hóa, nhưng mỗi giây dừng lại cũng sẽ làm mất 1 món hàng.

• Các trạm bảo vệ nằm tại các vị trí cố định trên con đường từ 0 đến \(h\), bao gồm cả điểm xuất phát (vị trí 0) và đích đến (vị trí kho hàng \(h\)). Tuy nhiên, tài xế không thể dừng lại ở bất kỳ vị trí nào ngoài các trạm bảo vệ. Nếu dừng ở các điểm ngoài trạm bảo vệ, hàng sẽ bị mất và đối thủ sẽ cướp.

Kho hàng cũng là trạm bảo vệ, nên khi đến kho, tài xế sẽ không bị mất hàng. Túi giao hàng chứa đủ số lượng hàng lớn, không thể mất hết.

Yêu cầu: Giúp tài xế giảm thiểu tối đa số lượng hàng bị mất trong suốt hành trình, đồng thời hoàn thành công việc giao hàng một cách hiệu quả nhất.

Dữ liệu vào

• Dòng đầu tiên chứa 4 số nguyên \(h,t,g,q (1 ≤ t ≤ h ≤10^12,1 ≤ g ≤10^6,1 ≤ q ≤ min(h,10^5)),\) với \(h\): vị trí kho hàng (quá trình giao hàng), \(t\): sau mỗi \(t\) giây, nếu tài xế không ở trong trạm bảo vệ, tài xế sẽ mất \(g\) món hàng, \(g\): Số món hàng bị mất do đối thủ cướp sau mỗi \(t\) giây không ở trạm bảo vệ, \(q\): Số lượng trạm bảo vệ trên đường đi.

• Dòng tiếp theo chứa \(q\) số nguyên \(a_1,a_2,...,a_q (0 = a_1 < a_2 < ...< a_q < h)\) là các vị trí của các trạm bảo vệ

Kết quả

• Một số nguyên duy nhất là số món hàng mà tài xế sẽ làm mất ít nhất trong suốt hành trình từ điểm xuất phát đến kho hàng.

Ràng buộc:

• Subtask 1 (10% số điểm): \(t ≤ 10^6\) và \(q = 1\)

• Subtask 2 (20% số điểm):\( h ≤ 10^3 \)

• Subtask 3 (25% số điểm): t ≤ 10^6 và q ≤ 10^3

• Subtask 4 (20% số điểm): \(t ≤ 10^2 \)

• Subtask 5 (15% số điểm): \(t ≤ 10^5\)

• Subtask 6 (10% số điểm): Không có ràng buộc gì thêm.

Sample Input

```` 18 4 5 3 0 8 15

## Sample Output

29 ```