სოჭის ოლიმპიადა

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

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

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

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

წყარო: IBSU, 2014, ზამთრის ოლიმპიადა, X-XII


 

როგორც ცნობილია, სოჭში ახლა ზამთრის ოლიმპიური თამაშები მიმდინარეობს, რომლის მოსამზადებელი სამუშაოებიც მნიშვნელოვანი ხარვეზებით წარიმართა, საკმაოდ ძვირიც დაჯდა და ზოგიერთმა იქაურმა ჩინოვნიკმა და ბიზნესმენმა ხელიც კარგად მოითბო (ანუ, ბლომად ფული იშოვეს :)).

ოლიმპიადის ჩასატარებლად N რაოდენობის ობიექტი იქნა აშენებული და ახლა რუსეთის მთავრობას სურს გაარკვიოს, რა თანხა დაჯდა ამ სამუშაოების შესრულება.

მშენებლობა K+1 დღე მიმდინარეობდა დაწყებული 0-ვანი დღიდან და დამთავრებული K -ური დღით. ამასთან, j-ური ობიექტის ღირებულება ნულოვან დღეს aj დოლარი იყო, მაგრამ ყოველ მომდევნო დღეს თითოეული ობიექტის ღირებულება შემდეგი წესით იზრდებოდა: j-ური ობიექტის ღირებულება i-ურ დღეს ხდებოდა ყველა იმ ობიექტების წინა დღის ღირებულებათა ჯამის ტოლი, რომელთა ნომრები j-ზე ნაკლები ან ტოლი იყო. სხვანაირად რომ ვთქვათ, Si,j = , სადაც Si,j წარმოადგენს j-ური ობიექტის ღირებულებას i-ურ დღეს. საბოლოოდ, j-ურ ობიექტზე დაიხარჯა SK,j დოლარი, ანუ მისი ღირებულება ბოლო K-ურ დღეს. ამ სიდიდეს j-ური ობიექტის საბოლოო ღირებულება ვუწოდოთ.

პროექტების ღირებულებათა ასეთი ზრდა სოჭის ოლიმპიადის მოსამზადებელი სამუშაოების დროს იშვიათობას არ წარმოადგენდა, მაგრამ გაგიკვირდებათ და, ეს ფულიც კი საკმარისი არ აღმოჩნდა! გაირკვა, რომ ერთ რომელიღაც i>0 დღეს ერთი რომელიღაც j-ური ობიექტის ღირებულება დამატებით კიდევ ჯერჯერობით უცნობი X თანხით გაიზარდა (ანუ, Si,j + X), რამაც, რა თქმა უნდა, ზეგავლენა მოახდინა მომდევნო დღეებში ობიექტების ფასებზე. სპეციალისტებმა გაარკვიეს, რომ ამის გამო ყველა ობიექტის საბოლოო ღირებულებათა ჯამი D დოლარით გაიზარდა და ახლა აინტერესებთ, რისი ტოლი შეიძლება იყოს X.

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

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

სტანდარტული შეტანის პირველ სტრიქონში მოცემულია თითო ჰარით გამოყოფილი სამი მთელი დადებითი N, K და D რიცხვი (1≤N,K≤105, 1≤D≤1018) ოლიმპიური ობიექტების რაოდენობა, ღირებულებების ზრდის დღეთა რაოდენობა და იმ თანხის რაოდენობა, რომლითაც უკანონოდ გაიზარდა ობიექტთა ჯამური ღირებულება (შესაბამისად). მომდევნო სტრიქონში ჩაწერილია თითო ჰარით გამოყოფილი N რაოდენობის მთელი ai რიცხვი (1≤ai≤109) - 0-ვან დღეს ობიექტთა ღირებულებები.

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

სტანდარტული გამოტანის ერთადერთ სტრიქონში გამოიტანეთ ერთი მთელი დადებითი რიცხვი – X-ის შესაძლო მინიმალური მნიშვნელობა.

 




მაგალითები

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

შენიშვნა

 

ტესტების 34%-ში N10, K10, ai10 და X-ის საძიებელი მნიშვნელობა არ აღემატება 10-ს;

ტესტების 26%-ში N≤1 000 , K≤1 000.