← 返回题目列表

Codeforces · 990/E

E. 柱灯

中文机器翻译题面 查看原题

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