题面描述

塔子哥接到一项任务，需要在一条长为 $N$ 公里的河流上监测水质。河流沿线有 $K$ 个候选地点适合建设水质监测站，每个监测站的覆盖半径为 $R$ 公里，建设一个监测站的成本为 $M$。任务是计算出最少需要多少经费才能覆盖整条河流，如果无法通过在所有候选地点建设监测站来实现覆盖，则输出 "-1"。输入包括河流长度、覆盖半径、建设成本以及候选地点的具体位置，输出则是最少经费或 "-1"。

思路

区间覆盖模板题目，这道题和区间覆盖的区别在于区间固定，我们使用贪心去解决对应的问题。

对于地址$i$，假设地址小于$i$的都已经被覆盖，那么如果我们需要覆盖它，我们可以选择的基站位置在范围$[i-R,i+R]$内。假设现在存在两个基站$x$和$y$$(y>x)$都满足对应的要求，那么我们更偏向于选择$y$基站，因为$y>x$，这样$y$的基站可以比$x$基站覆盖更多后面的地址。

题目描述

小明接到一个新课题，监测一整条河流的水质。

目前小明选择了一条河流进行水质监测，长度为 $N$ 公里。经过专业人员勘察，河流沿线有 $K$ 个候选地点适合安装水质监测站，每个监测站可以覆盖的长度为半径 $R$ 公里，单个监测站建设成本为 $M$ 。

假设小明知道的河流是一条直线，请计算最少需要多少经费建设水质监测站才能完成对整条河流(也就是直线上的每一个实数点)的水质监测。

输入描述

输入第一行包含三个整数 $N$ , $R$ , $M$ .($1 \leq N \leq 3000$,$10 \leq R \leq 200,1 \leq M \leq 100000$ ) 输入第二行包含 $K$ 个整数 $a_1,a_2…a_K$ ,表示在高铁沿线的第$a_1，a_2…a_K$ 公里的地点可以建设基站.( $1 \leq K \leq N,0 \leq a_i \leq N$ )

输出描述

输出一个整数，表示最少花费的经费，如果所有候选地点均建设了基站还是无法覆盖则输出 "-1" 。

样例1

样例输入

100 20 114514
10 30 50

样例输出

-1

样例2

样例输入

80 50 114514
0 20 40 60

样例输出

114514