B.优惠旅行

题目描述

张三要进行 $N$天的旅行，第 $i$天的费用为 $A_i$ 。他还可以使用优惠券，可以免除 $D$天(不用连续)的费用，价格为 $P$ 。如果剩余 $2$天，优惠券的作用是 $3$天，那么依然可以使用。

求这 $N$天旅行的最小费用。

输入格式

第一行有 $3$ 个整数 $N , D , P$

第二行有 $N$ 个整数，第 $i$ 个为 $A_i$

输出格式

输出最小花费

样例

5 2 10
7 1 6 3 6

20

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

3000000000

数据范围与提示

• $1 \leq N \leq 2*10^5$
• $1 \leq D \leq 2*10^5$
• $1 \leq P \leq 10^9$
• $1 \leq A_i \leq 10^9$

样例一解释

• 使用一张优惠券免除 $1,3$ 天的费用，总费用为 $1+3+6+10 = 20$ 。