rt。

题目描述

Adilbek 的家位于一个可以被表示为 OX 轴的街道上，这条街真的很黑，所以 Adilbek 想要安装一些柱灯来照亮它。街道上有 $n$ 个可以安装柱灯的位置，这些位置在 OX 轴上对应 $0,\dots,n-1$。但是有一些位置上有障碍物，不能放置安装柱灯。

有若干种不同的柱灯，它们有且仅有功率不同。当一个功率为 $l$ 的柱灯被安装在位置 $x$ 上时，这个柱灯可以照亮区间 $[x,x+l]$，所有柱灯的功率都是正整数。

柱灯店提供功率从 $1$ 到 $k$ 的柱灯，每种柱灯有无限个。然而，每个顾客只能购买一种功率的柱灯，一个功率为 $l$ 的柱灯的价格为 $a_l$。

现在，Adibek 想要知道，他购买一种柱灯来照亮整个 $[0,n]$ 的街道的最低花费是多少。Adibek 并不在乎这些灯是否会照亮街道的任何其他部分，例如，他可能在位置 $n-1$ 上安装一个功率为 $3$ 的柱灯（即使它的照明区域并不完全属于 $[0,n]$）。

输入格式

第一行有 $3$ 个整数 $n,m,k$（$1\le k\le n\le 10^6$，$0\le m\le n$）——分别表示街道的长度，障碍物的数量，柱灯的种类数。

第二行有 $m$ 个整数 $s_1,s_2,\dots,s_m$（$0\le s_1<s_2<\dots s_m<n$）——障碍物的位置。

第三行 $k$ 个整数 $a_1,a_2,\dots,a_k$（$1\le a\le 10^6$）——每种功率的柱灯的价格。

输出格式

输出 Adilbek 照亮街道 $[0,n]$ 的最小的花费，如果无论如何都无法照亮，输出 $-1$。

### 题目描述

Adilbek 的家位于一个可以被表示为 OX 轴的街道上，这条街真的很黑，所以 Adilbek 想要安装一些柱灯来照亮它。街道上有 $n$ 个可以安装柱灯的位置，这些位置在 OX 轴上对应 $0,\dots,n-1$。但是有一些位置上有障碍物，不能放置安装柱灯。

有若干种不同的柱灯，它们有且仅有功率不同。当一个功率为 $l$ 的柱灯被安装在位置 $x$ 上时，这个柱灯可以照亮区间 $[x,x+l]$，所有柱灯的功率都是正整数。

柱灯店提供功率从 $1$ 到 $k$ 的柱灯，每种柱灯有无限个。然而，每个顾客只能购买一种功率的柱灯，一个功率为 $l$ 的柱灯的价格为 $a_l$。

现在，Adibek 想要知道，他购买一种柱灯来照亮整个 $[0,n]$ 的街道的最低花费是多少。Adibek 并不在乎这些灯是否会照亮街道的任何其他部分，例如，他可能在位置 $n-1$ 上安装一个功率为 $3$ 的柱灯（即使它的照明区域并不完全属于 $[0,n]$）。

### 输入格式

第一行有 $3$ 个整数 $n,m,k$（$1\le k\le n\le 10^6$，$0\le m\le n$）——分别表示街道的长度，障碍物的数量，柱灯的种类数。

第二行有 $m$ 个整数 $s_1,s_2,\dots,s_m$（$0\le s_1<s_2<\dots s_m<n$）——障碍物的位置。

第三行 $k$ 个整数 $a_1,a_2,\dots,a_k$（$1\le a\le 10^6$）——每种功率的柱灯的价格。

### 输出格式

输出 Adilbek 照亮街道 $[0,n]$ 的最小的花费，如果无论如何都无法照亮，输出 $-1$。