该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

AT_abc318_c [ABC318C] Blue Spring

题目描述

题意简述

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

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

输入格式

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

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

输出格式

$1$ 个整数，如题意。

样例 1

输入

5 2 10
7 1 6 3 6

输出

20

样例 2

输入

3 1 10
1 2 3

输出

6

样例 3

输入

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

输出

3000000000

说明/提示

• $1 \le N \le 2 \times 10^5$
• $1 \le D \le 2 \times 10^5$
• $1 \le P \le 10^9$
• $1 \le F_i \le 10^9$

样例一解释

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

样例三解释

使用 $3$ 张优惠券，费用为 $3 \times 1000000000=3000000000$