მანქანები

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

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

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

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

წყარო: პოლონეთი, ოლიმპიადა 12, ეტაპი 1


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

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

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

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

·         სტანდარტული ინფუთიდან იღებს სტრინგს მანქანების მიმდევრობისა , რომლებითაც ჯასიოს თამაში მოუნდება.

·         დაითვლის მინიმალურ რაოდენობას მანქანებისა, რომელთა ჩამოღებაც დასჭირდება დედას თაროდან.

·         გამოიტანს მიღებულ პასუხს სტანდარტული აუთფუთით.

 შემომავალი მონაცემები: პირველ ხაზზე შემოდის სამი ინტი: n,k, p (1 ≤ k ≤ n ≤ 100 000 , 1 ≤ p ≤500 000) , ერთი სფეისით დაშორებული . ესენია ყველა მანქანის რაოდენობა , იატაკზე არსებულ მანქანათა მაქსიმალური რაოდენობა , და იმ მიმდევრობის სიგრძე , რომელშიც არის მანქანები , რომლებითაც ჯასიოს თამაშები მოუნდება. შემდეგი p ხაზი შეიცავლს ერთცალ ინტს , რომელიც აღნიშვნავს იმ მანქანის ნომერს, რომლითაც ჯასიოს თამაში მოუნდება.

 გამოსატანი მონაცემები: სტანდარტული აუთფუთით გამოიტანეთ ერთი რიცხვი - ჯასიოს დედის მიერ თაროდან ჩამოღებული მანქანების მინიმალური რაოდენობა .




მაგალითები

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