Sóc vừa hái những quả sầu riêng giúp mẹ xong nên đã đến lúc về nhà. Sóc đang đứng ở vị trí \(0\) và đi một đường thẳng về nhà ở vị trí \(h\) với khoảng cách là \(h\) mét, được biết khi đi mỗi giây sóc đi được đúng \(1\) mét, có thể biểu diễn trên trục \(Ox\) với vị trí sóc đang đứng là gốc tọa độ \(x = 0\) còn nhà sóc ở vị trí \(x = h\).

Tuy nhiên đường đi không thuận lợi như sóc nghĩ, mỗi \(1\) giây sóc làm rơi \(1\) quả sầu riêng, và cứ \(t\) giây từ khi bắt đầu sóc bị lại trộm mất \(g\) quả. Nhưng may thay, có \(q\) trạm bảo vệ ở trên đường lần lượt ở các vị trí: \(a_{1}, a_{2}, \ldots, a_{q}\) và vị trí \(0\) luôn là trạm bảo vệ \((a_{1} = 0)\). Sóc có thể dừng lại nghỉ ngơi tại các trạm bảo vệ với số giây bất kỳ (số giây phải là số nguyên), tuy nhiên không được dừng tại bất kỳ vị trí nào khác. Tại các trạm bảo vệ sóc sẽ không bị trộm mất sầu riêng ở bất kỳ thời gian nào nhưng vẫn bị rơi sau mỗi giây. Ngoài ra, nhà của sóc cũng giống như trạm bảo vệ nên khi ở trong nhà sóc cũng sẽ không bị trộm. (Xem phần giải thích ví dụ để hiểu rõ hơn)

Hãy giúp sóc về đến nhà mà bị mất ít quả sầu riêng nhất nhé, được biết túi sóc đựng một số lượng sầu riêng rất lớn và không thể nào bị rớt và trộm hết.

Input

• Dòng đầu tiên chứa bốn số nguyên \(h\), \(t\), \(g\) và \(q\) \((1 \leq t < h \leq 10^{12}, 1 \leq g \leq 10^6, 1 \leq q \leq \min(h, 10^5))\), với \(h\) là vị trí nhà của sóc, và cứ \(t\) giây thì nếu sóc không ở trong trạm bảo vệ thì bị mất \(g\) quả và cuối cùng là \(q\) là số lượng trạm trú ẩn.
• Dòng tiếp theo chứa \(q\) số nguyên \(a_{1}, a_{2}, \ldots, a_{q}\) \((0 = a_{1} < a_{2} < \ldots < a_{q} < h)\) là các trạm trú ẩn.

Output

• Một số nguyên duy nhất là số quả sầu riêng mà sóc làm rơi và bị trộm mất là ít nhất.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(t \le 10^6\) và \(q = 1\).
• Subtask \(2\) (\(20\%\) số điểm): \(h \le 10^3\).
• Subtask \(3\) (\(25\%\) số điểm): \(t \le 10^6\) và \(q \le 10^3\).
• Subtask \(4\) (\(20\%\) số điểm): \(t \le 10^2\).
• Subtask \(5\) (\(15\%\) số điểm): \(t \le 10^5\).
• Subtask \(6\) (\(10\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

18 4 5 3
0 8 15

Output

29

Note

• Ở cách này, sóc đi một mạch mà không dừng ở bất kỳ đâu hết \(18\) giây nên bị rớt mất \(18\) quả và ở giây thứ \(4, 12, 16\) sóc không ở trong trạm bảo vệ nên sóc bị trộm mất \(3 \times g = 15\) quả nữa. Vậy nên ở trường hợp này sóc bị mất tổng cộng \(18 + 15 = 33\).

• Ở cách này, sóc dừng lại ở trạm \(a_{3} = 15\) một giây cho nên tổng thời gian sóc đi là \(19\) giây nên bị rớt mất \(19\) quả và ở giây thứ \(4, 12\) sóc không ở trong trạm bảo vệ nên sóc bị trộm mất \(2 \times g = 10\) quả nữa. Vậy nên ở trường hợp này sóc bị mất tổng cộng \(19 + 10 = 29\).

Test 2

Input

18 10 100 3
0 8 15

Output

20

Note

• Nếu sóc đi thẳng một mạch thì sóc sẽ mất \(118\) quả vì đi hết \(18\) giây và ở giây thứ \(10\) sóc ở vị trí \(10\) không nằm trong trạm bảo vệ nào nên bị trộm mất \(100\) quả sầu riêng nữa.
• Sóc sẽ đi một cách khôn ngoan hơn bằng cách, dừng lại ở trạm \(a_{1} = 0\) trong \(2\)s và di chuyển một mạch về nhà. Nhờ đó ở giây thứ \(10\) sóc ở vị trí \(8\) và ở đó có trạm bảo vệ nên sóc không bị trộm mất quả sầu riêng nào nên tổng số quả sầu riêng bị mất là \(2 + 18 + 0 = 20\).

352 24 54 1
0

1108

20 5 4 4
0 5 10 15

20

65 20 100 4
0 14 25 33

172