记忆碎片

题目背景

在一条破碎的时间线上，记录着 $N$ 个连续的记忆碎片。第 $i$ 个记忆碎片有一个时间戳 $A_i$。由于时间线受到了干扰，一些记忆碎片的时间戳可能出现了异常。为了恢复时间线，你可以对部分记忆碎片进行校准，然后将整条时间线划分成若干连续章节。

题目描述

给定一个长度为 $N$ 的非负整数数组 $A$，你最多可以修改 $K$ 个元素。每次修改可以选择一个位置 $i$，并将 $A_i$ 改成任意整数，每个位置最多被修改一次。

修改完成后，你需要将数组划分成恰好 $P$ 个连续的非空子段。每个元素必须恰好属于一个子段，子段之间不能重叠，不能改变元素的原有顺序。

对于一个子段，其代价定义为：子段内最大值 − 子段内最小值。一个划分方案的总代价定义为：所有子段代价中的最大值。

请你求出，在最多修改 $K$ 个元素的情况下，能够得到的最小总代价。

输入格式

第一行三个整数 $N, P, K$（$1 \le N \le 500$，$1 \le P \le 50$，$0 \le K \le N$）。

第二行 $N$ 个非负整数 $A_1, A_2, \dots, A_N$（$0 \le A_i \le 10^9$）。

输出格式

输出一个整数，表示所有合法修改与划分方案中能够得到的最小总代价。

样例

8 3 2
1 10 11 12 2 3 100 101

1