Con đường từ nhà PMT đến trường LHP là một đường thẳng có thể biểu diễn trên trục toạ độ Ox. Nhà của PMT đặt tại điểm 0 còn trường LHP tại điểm nguyên dương N trên trục toạ độ. Tuy nhiên, vào buổi đêm, con đường này rất tối vì không có một bóng đèn nào. Do đó, PMT đề nghị nên lắp đèn cho đoạn đường này. Trên trục toạ độ, chỉ có thể đặt bong đèn tại các vị trí nguyên dương trên trục toạ độ từ điểm  [0,…, N-1]. Tuy nhiên, có một số vị trí bị cấm đặt điện đường. Có rất nhiều loại điện đường khác nhau, mỗi loại có một công suốt và giá khác nhau. Loại điện có công xuất là P nếu đặt tại vị trí x thì có thể chiếu sáng đoạn [ x, x + P].

Cửa hàng cung cấp điện có vô số bóng điện mỗi loại. Tuy nhiên, cửa hàng yêu cầu PMT chỉ được mua một loại bong duy nhất và có thể mua vô số bóng loại như vậy.

Hãy giúp PMT tìm cách mua loại điện phù hợp và cách lắp tốt nhất sao cho chí phí để chiếu sáng toàn bộ con đường là nhỏ nhất.

Input

Dòng 1 chứa 3 số nguyên N,M,K ( 1 <= K <= N <= 10^6, 0 <= M <= N): chiều dài con đường PMT muốn chiếu sáng, số vị trí bị cấm lắp điện và công suất của các loại điện trong của hàng là từ 1 tới K.

Dòng 2 cứa M số nguyên dương là các vị trí cấm lắp điện.

Dòng 3 chưa K số, số thứ i là s[i] (s[i] <= 10^6) : giá của loại đèn có công suốt là i.

Output

Chi phí ít nhất để chiếu sáng toàn bộ con đường. Nếu không thể chiếu sáng được toàn bộ, in ra -1.