У вас есть длинная палка, состоящая из \(m\) отрезков, пронумерованных от \(1\) до \(m\). Каждый отрезок имеет длину равную \(1\) сантиметру. Однако, некоторые отрезки сломались и требуют починки.
У вас также есть бесконечно-длинная ремонтная лента. Вы хотели бы вырезать несколько кусочков из этой ленты так, чтобы покрыть все сломанные отрезки. В частности, если разместить кусок ленты целой длины \(t\) в позиции \(s\), то отрезки \(s, s+1, \ldots, s+t-1\) окажутся покрытыми.
Разрешается покрывать не сломанные отрезки, также допускается, что какие-то кусочки ленты будут пересекаться.
Как говорится, время — деньги, поэтому вы хотите покрыть все сломанные отрезки, вырезав не более \(k\) кусочков ленты. Какую минимальную суммарную длину этих кусочков нужно вырезать?
Выходные данные
Выведите минимальную суммарную длину кусочков ленты.
Примечание
В первом примере вы можете использовать кусок длины \(11\), чтобы покрыть сломанные отрезки \(20\) и \(30\), и ещё один кусок длины \(6\), чтобы покрыть \(75\) и \(80\), так что суммарная длина равна \(17\).
Во втором примере вы можете вырезать кусок длины \(4\), чтобы покрыть сломанные отрезки \(1\), \(2\), \(4\), и два куска длины \(1\), чтобы покрыть \(60\) и \(87\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 100 2
20 30 75 80
|
17
|
|
2
|
5 100 3
1 2 4 60 87
|
6
|