გლუვი ლანდშაფტი

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 256 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: USACO, 2004/05, OPEN


ბუბა აწყობს ლაშქრობას საკუთარი ფერმის ტერიტორიაზე და ამიტომ სურს, რომ 
გახადოს ის უფრო გლუვი. თუმცა ეს ოპერაცია საკმაოდ ძვირი ჯდება და ამიტომ
უნდა, რომ რაც შეიძლება ნაკლები მიწა მოიშოროს. 
    ფერმა აღიწერება ორგანზომილებიანი პროფილით ანუ  N (1 <= N <= 1000) მთელი 
რიცხვისაგან შედგენილი ერთგანზომილებიანი მასივით (რიცხვების დიაპაზონია 1..1,000,000). 
მასივის მაგალითი შეიძლება ასეთი იყოს:

1 2 3 3 3 2 1 3 2 2 1 2,

    მოცემული მასივი აღწერს ფერმის სიმაღლეთა შემდეგ პროფილს:

    * * *     *
  * * * * *   * * *   *
* * * * * * * * * * * *
1 2 3 3 3 2 1 3 2 2 1 2

     ერთი ან მეტი თანაბარი სიმაღლისაგან შედგენილ უწყვეტ ნაკვეთს ამ მასივში 
ეწოდება "პიკი", თუკი ამ ნაკვეთის მარცხენა და მარჯვენა საზღვრები წარმოადგენენ 
ან მასივის საზღვარს, ან ელემენტს, რომელიც პიკზე დაბლაა. ზემოთ მოყვანილ
მაგალითში არსებობს სამი პიკი. 
     განსაზღვრეთ მიწის მინიმალური რაოდენობა (სიმაღლის ყოველი ერთეული 
მიწის ერთეულს შეესაბამება), რომლის მოშორებაც აუცილებელია საიმისოდ, რომ 
დარჩენილი პროფილი შეიცავდეს არა უმეტეს K (1 <= K <= 25) პიკს.
     შევნიშნოთ, რომ სიმაღლეები შეიძლება შევამციროთ, მაგრამ არ შეიძლება გავზარდოთ.
     თუკი ზემოთ მოყვანილ მაგალითში საჭიროა 1 პიკის დატოვება, მაშინ ოპტიმალური 
ამოხსნაა - მოვიშოროთ მიწის  2 + 1 + 1 + 1 = 5 ერთეული, რათა მივიღოთ ასეთი პროფილი:

    * * *     -
  * * * * *   - - -   -
* * * * * * * * * * * *
1 2 3 3 3 2 1 1 1 1 1 1

სადაც '-' აღნიშნავს მოშორებულ მიწას.

შეტანის ფორმატი:
* სტრიქონი 1: ჰარით გაყოფილი ორი მთელი რიცხვი  N და  K.
* სტრიქონები 2..N+1: ყოველი სტრიქონი შეიცავს ერთ მთელ რიცხვს  - სიმაღლეს.  (i+1)-ე სტრიქონი შეიცავს i-ურ სიმაღლეს.

გამოტანის ფორმატი:
* სტრიქონი 1: მოსაშორებელი მიწის მინიმალური რაოდენობა, რომლის შემდეგაც  დარჩება K პიკი.



მაგალითები

შესატანი მონაცემები
12 1 1 2 3 3 3 2 1 3 2 2 1 2 დაკოპირება
გამოსატანი მონაცემები
5 დაკოპირება