რკინიგზის სადგური

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

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

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

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


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

 

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

პირველ ხაზში ორი მონაცემი n და  k (1 ≤ n ≤ 1051 ≤ k ≤ 104) , რიგში მდგომთა რიცხვი და სალაროების რაოდენობა. შემდეგ ხაზში  n-ცალი ti (1 ≤ ti ≤ 105), დრო რომელიც საჭიროა ბილეთის შესაძენად.

 

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

ერთი მთელი რიცხვი: დრო, რომელიც საჭიროა რიგის დასაცლელად.




მაგალითები

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