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

题目背景

慕雪少年发现了一条神秘的时间回廊，回廊中有 $n$ 个时间节点，每个节点有一个时间值 $t_i$。他可以在节点间移动，但移动会消耗"时间能量"，消耗量与时间差值有关。他需要规划一条路径，以最小的总能量访问所有节点。

题目描述

有 $n$ 个时间节点，第 $i$ 个节点的时间值为 $t_i$（互不相同）。慕雪少年初始在节点 $1$，需要访问所有节点恰好一次，最终必须回到起点 $1$。

从节点 $i$ 移动到节点 $j$ 消耗的能量为：$|t_i - t_j|^p$，其中 $p$ 是给定的常数。

此外，有一个特殊规则：如果访问顺序中连续三个节点 $a \rightarrow b \rightarrow c$ 满足 $t_a < t_b < t_c$ 或 $t_a > t_b > t_c$，则会触发"时间共振"，获得额外能量奖励 $R$（即总能量减少 $R$）。

求访问所有节点的最小总能量。

输入格式

• 第一行：$n, p, R$ ($3 \leq n \leq 18$, $1 \leq p \leq 3$, $0 \leq R \leq 10^6$)
• 第二行：$n$ 个整数 $t_1, t_2, \dots, t_n$ ($1 \leq t_i \leq 10^9$，互不相同)

输出格式

一个整数，表示最小总能量。

输入输出样例 #1

输入 #1

4 1 10
5 2 8 1

输出 #1

4

数据范围