2016-17 Woburn Challenge Finals Round - Senior Division

It's almost time to head into battle, but Bo Vine's cow soldiers insist
on taking a nice long drink of water first. All
of his army's cows have lined up at a trough to drink water. However,
the cows like their privacy when drinking, and the
-th cow insists
that they must drink from a trough from which at most
other cows are also drinking.
The cows refuse to budge until they get hydrated, so to help make that
possible, Bo Vine is prepared to install at most
dividers at various points along the trough, effectively dividing it
into multiple troughs as far as the cows are concerned. For example, if
he installs a single divider between cows
and
, then cows
will be considered to drink from one trough, while cows
will be considered to drink from a different trough.
It may turn out that the cows' demands can't all be met even after the
installation of
dividers. As such, Bo Vine may also need to
"encourage" some of them to relax their requirements. Each cow is
willing to increase their
value by
in exchange for
treat. Bo
Vine may bribe any cow as many times as he'd like.
What's the minimum total number of treats which Bo Vine must give to the
cows such that, once at most
dividers are installed, each cow will
be willing to drink from its trough?
In test cases worth
of the points,
and
.
In test cases worth another
of the points,
.
Input Specification
The first line of input consists of two space-separated integers
and
.
lines follow, the
-th of which consists of a single integer
(for
).
Output Specification
Output one line consisting of a single integer - the minimum total
number of treats required such that the cows can all be satisfied after
the installation of
dividers.
Sample Input
Copy
7 2
2 0 5 0 1 3 1
Sample Output
Copy
3
Sample Explanation
One optimal strategy is to give the second cow
treats to increase its
value from
to
, and the fourth cow
treat to increase its
value from
to
. Then, Bo Vine can install one divider between cows
and
, and one more between cows
and
, in order to yield the
following valid set of troughs:
Copy
[ 2 2 5 | 1 1 | 3 1 ]
Comments