წყალი და ვედროები

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

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

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

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

წყარო: BULG, 2009/10, დასკვნითი, 6


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

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

შესატანი მონაცემები: პირველ სტრიქონში ორი მთელი რიცხვი - n და k. მეორე სტრიქონში n ცალი მთელი რიცხვი - ვედროების ტევადობები ლიტრებში. 

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

შეზღუდვები:

     1 ≤ n ≤ 100 000

     1 ≤ k ≤ 1 000 000 000

     0< i-ური ვედროს ტევადობა ლიტრებში ≤ k




მაგალითები

შესატანი მონაცემები
6 9 5 9 7 8 4 3 დაკოპირება
გამოსატანი მონაცემები
5 დაკოპირება