Post Lamps

Adilbek의 집은 OX축으로 나타낼 수 있는 거리에 있다. 이 거리는 매우 어두워서 Adilbek은 거리를 밝히기 위해 가로등을 몇 개 설치하려 한다. 거리에는 가로등을 설치할 수 있는 위치가 n개 있으며, 이 위치들은 OX축에서 0부터 n - 1까지의 정수에 대응한다. 하지만 일부 위치는 막혀 있어 그곳에는 가로등을 설치할 수 없다.

가로등에는 밝히는 범위만 서로 다른 여러 종류가 있다. 위치 x에 설치하면, 밝히는 범위가 l인 가로등은 구간 [x; x + l]을 밝힌다. 각 가로등이 밝히는 범위는 항상 양의 정수이다.

가로등 상점에서는 밝히는 범위가 1부터 k까지인 각 종류의 가로등을 무한히 제공한다. 하지만 각 고객은 정확히 한 종류의 가로등만 주문할 수 있다. 밝히는 범위가 l인 가로등은 하나당 $a_l$의 비용이 든다.

Adilbek이 정확히 한 종류의 가로등만 구매하여 거리의 전체 구간 [0; n]을 밝히는 데 필요한 총비용의 최솟값은 얼마인가? 일부 가로등이 거리의 다른 구간도 밝히는 것은 Adilbek에게 중요하지 않으므로, 예를 들어 밝히는 범위가 3인 가로등을 위치 n - 1에 설치해도 된다(그 가로등이 밝히는 영역이 구간 [0; n]에 완전히 포함되지 않더라도).

첫 번째 줄에 세 정수 n, m, k (1 ≤ k ≤ n ≤ $10^6$, 0 ≤ m ≤ n)가 주어진다. 이는 각각 Adilbek이 밝히려는 거리 구간의 길이, 막힌 위치의 수, 사용할 수 있는 가로등이 밝히는 범위의 최댓값이다.

두 번째 줄에 막힌 위치를 나타내는 m개의 정수 $s_1$, $s_2$, ..., $s_m$ (0 ≤ $s_1$ < $s_2$ < ... $s_m$ < n)가 주어진다.

세 번째 줄에 가로등의 비용을 나타내는 k개의 정수 $a_1$, $a_2$, ..., $a_k$ (1 ≤ $a_i$ ≤ $10^6$)가 주어진다.

Adilbek이 정확히 한 종류의 가로등만 구매하여 거리의 전체 구간 [0; n]을 밝히는 데 필요한 총비용의 최솟값을 출력한다.

전체 구간 [0; n]을 밝힐 수 없다면 -1을 출력한다.