გიორგის პატარაობაში სამშენებლო ბლოკებით თამაში უყვარდა. თავიდან ის ბლოკებს სვეტებში შემთხვევითი სიმაღლით აწყობდა, შემდეგ კი ცდილობდა ისისნი შემდეგნაირად დაელაგებინა: გიორგი ირჩევდა რაღაც  k რიცხვს და ცდილობდა ბლოკები დაეწყო ისე, რომ რომელიმე თანმიმდევრობით განლაგებული k სვეტი თანაბარი სიმაღლის ყოფილიყო. გარდა ამისა, ის ცდილობდა მიეღწია ამ მიზნისთვის სვლების მინიმალური რაოდენობით, სადაც ერთ სვლად ითვლება:

• ნებისმიერი სვეტის თავზე ერთი ბლოკის განთავსება(გიორგის აქვ უზარმაზარი ყუთი, რომელშიც აწყვია უსასრულო რაოდენობის ბლოკები, შესაბამისად ყოველთვის შესაძლებელი იქნება ამ სვლის გაკეთება) , ან
• ზედა ბლოკის აღება ნებისმიერი სვეტიდან

თუმცა გიორგი არასოდეს იყო დარწმუნებული იმაში, იყო თუ არა მისი სვლების თანმიმდევრობა ოპტიმალური, ამიტომ მან გთხოვათ თქვენ ისეთი პროგრამის დაწერა, რომელიც მას ამ პრობლემის გადაჭრაში დაეხმარება.

დაწერეთ პროგრამა, რომელიც:

• კითხულობს k რიცხვს ბლოკების საწყის განლაგებასთან ერთად
• საზღვრავს ოპტიმალურ ამოხსნას (სვლების უმოკლესი შესაძლო თანმიმდევრობა)
• გამოაქვს პასუხი

 შესატანი მონაცემები:

პირველ სტრიქონში შემოდის სფეისით გამოყოფილი ორი ინთეჯერი, n და k , სადაც (1 <= k <= n <= 100000) .  მომდევნო n  სტრიქონი შეიცავს რომელიღაც სვეტის სიმაღლეს;  i+1-ე სტრიქონი შეიცავს ერთ ინთეჯერს 0 <= hi <= 1000000 -  i-ური სვეტის სიმაღლე, ანუ იმ ბლოკების რაოდენობა, რომლებიც ამ სვეტის შემადგენლობაში შედის.

 გამოსატანი მონაცემები:

უნდა გამოვიტანოთ ოპტიმალური ამოხსნა, ბლოკების ისეთი განლაგება, რომელიც:

• შეიცავს k ცალ თანმიმდევრობით განლაგებულ ტოლი სიმაღლის სვეტებს
• მიიღება თავდაპირველი ბლოკების წყობიდან მინიმალური სვლების გაკეთების მეშვეობით

ყოველი n+1 გამოსატანი ხაზი უნდა შეიცავდეს ერთ ინთეჯერს. პირველ სტრიქონში უნდა გამოვიტანოთ მინიმალური სვლების რაოდენობა, რომელიც დაგვჭირდა სასურველი შედეგის მისაღებად. i+1-ე სტრიქონი, სადაც (1<= i <= n), უნდა შეიცავდეს რიცხვს - hi, რომელიც არის  i-ური სვეტის საბოლოო სიმაღლე. თუ არსებობს ერთზე მეტი ოპტიმალური ამოხსნა გამოიტანეთ ნებისმიერი მათგანი.

მაგალითები

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

გამოსატანი მონაცემები
2
3
9
2
2
2
                  დაკოპირება