Post Lamps

题意翻译

### 题目描述 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'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] $ ).

输入输出格式

输入格式


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 < s_2 < \dots s_m < 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.

输出格式


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.

输入输出样例

输入样例 #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