Adilbek 的房子位于一条可以用 OX 轴表示的街道上。这条街真的很黑,所以阿迪贝克想安装一些柱灯来照亮它。街道有$$$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 \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 < s_2 < \dots s_m < n$$$) — 被锁定的仓位。
第三行包含 $$$k$$$ 整数 $$$a_1, a_2, \dots, a_k$$$ ($$$1 \le a_i \le 10^6$$$) — 柱灯的成本。
输出
打印 Adilbek 可以购买的一种类型的柱灯的最低总成本,用于照亮整个路段 $$$[0; n]$$$ 的街道。
如果照亮整个段 $$$[0; n]$$$ 不可能,打印 -1。
示例
输入 #1
6 2 3 1 3 1 2 3
输出 #1
6
输入 #2
4 3 4 1 2 3 1 10 100 1000
输出 #2
1000
输入 #3
5 1 5 0 3 3 3 3 3
输出 #3
-1
输入#4
7 4 3 2 4 5 6 3 14 15
输出#4
-1