CF990E.Post Lamps

Adilbek's house is located on a street which can be represented as the OX axis. This street is really dark, so Adilbek wants to install some post lamps to illuminate it. Street has $n$ positions to install lamps, they correspond to the integer numbers from $0$ to $n - 1$ on the OX axis. However, some positions are blocked and no post lamp can be placed there.

There are post lamps of different types which differ only by their power. When placed in position $x$, post lamp of power $l$ illuminates the segment $[x; x + l]$. The power of each post lamp is always a positive integer number.

The post lamp shop provides an infinite amount of lamps of each type from power $1$ to power $k$. Though each customer is only allowed to order post lamps of exactly one type. Post lamps of power $l$ cost $a_l$ each.

What is the minimal total cost of the post lamps of exactly one type Adilbek can buy to illuminate the entire segment $[0; n]$ of the street? If some lamps illuminate any other segment of the street, Adilbek does not care, so, for example, he may place a lamp of power $3$ in position $n - 1$ (even though its illumination zone doesn't completely belong to segment $[0; n]$).

阿迪尔别克的家位于一条可以表示为 $OX$ 轴的街道上。这条街道非常昏暗，因此阿迪尔别克希望安装若干路灯来照亮它。街道上有 $n$ 个可安装路灯的位置，它们对应于 $OX$ 轴上从 $0$ 到 $n - 1$ 的整数坐标。然而，其中一些位置被阻挡，无法在这些位置安装路灯。

路灯有不同类型，但彼此之间仅在功率上有所区别。当将一个功率为 $l$ 的路灯安装在位置 $x$ 时，它所照亮的区间为 $[x; x + l]$。每个路灯的功率恒为正整数。

路灯商店提供功率从 $1$ 到 $k$ 的各类路灯，且每种功率的路灯数量均为无限。但每位顾客仅允许订购恰好一种功率的路灯。功率为 $l$ 的路灯单价为 $a_l$。

阿迪尔别克需要购买恰好一种功率的若干路灯，以最低总成本照亮整条街道上的区间 $[0; n]$。若某些路灯照亮了 $[0; n]$ 以外的其他路段，阿迪尔别克并不在意；例如，他可以在位置 $n - 1$ 安装一个功率为 $3$ 的路灯（即使其照明区域并未完全落在区间 $[0; n]$ 内）。

The first line contains three integer numbers $n$, $m$ and $k$ ($1 \le k \le n \le 10^6$, $0 \le m \le n$) — the length of the segment of the street Adilbek wants to illuminate, the number of the blocked positions and the maximum power of the post lamp available.

The second line contains $m$ integer numbers $s_1, s_2, \dots, s_m$ ($0 \le s_1 \lt s_2 \lt \dots s_m \lt n$) — the blocked positions.

The third line contains $k$ integer numbers $a_1, a_2, \dots, a_k$ ($1 \le a_i \le 10^6$) — the costs of the post lamps.

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le k \le n \le 10^6$，$0 \le m \le n$）——分别表示 Adilbek 想要照亮的街道区段长度、被阻挡的位置数量以及可用路灯的最大功率。

第二行包含 $m$ 个整数 $s_1, s_2, \dots, s_m$（$0 \le s_1 \lt s_2 \lt \dots \lt s_m \lt n$）——表示被阻挡的位置。

第三行包含 $k$ 个整数 $a_1, a_2, \dots, a_k$（$1 \le a_i \le 10^6$）——表示各路灯的费用。

Print the minimal total cost of the post lamps of exactly one type Adilbek can buy to illuminate the entire segment $[0; n]$ of the street.

If illumintaing the entire segment $[0; n]$ is impossible, print -1.

输出阿迪尔别克恰好购买一种类型的路灯以照亮整条街道区间 $[0; n]$ 所需的最小总成本。

如果无法照亮整条街道区间 $[0; n]$，则输出 $-1$。