ტაქსები

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

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

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

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

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


  ბაიტეზარს სურს ტაქსით მგზავრობა ქალაქ ბაიტოტურადან ქალაქ ბაიტოდულში. ქალაქებს შორის მანძილი m კმ-ია. ამ ქალაქებს შორის გზაზე, ბაიტოდურადან d კმ-ის დაშორებით არის ტაქსების ბაზა, სადაც არის n  ცალი ტაქსი, რომლებიც გადანომრილები არიან 1 დან n – მდე. თითოეულ ტაქსს აქვს საწვავის განსაზღვრული მარაგი, რომლითაც შეუძლია xi   კილომეტრ მანძილის დაფარვა.

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

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

 პირველ ხაზზე : სფეისით დაშორებული სამი მთელი რიცხვი: m (მანძილი ქალაქებს შორის), d (მანძილი ბაიტოტურადან ტაქსების ბაზამდე) , n (ტაქსების რაოდენობა) (1 <= d <= m <= 10^18, 1 <= n <= 500 000).

 მეორე ხაზზე : სფეისით დაშორებული n ცალი მთელი რიცხვი (x1,x2...xn), თითოეული  აღნიშნავს მაქსიმალურ მანძილს რისი დაფარვაც i-ურ ტაქსს შეუძლია. (1 <= xi <= 10^18)

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

 

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

თუ მიღწევა შეუძლებელია მაშინ გამოიტანეთ 0.

 

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

https://szkopul.edu.pl/problemset/problem/Sa5HmhgGMPHhB6qXqPv1asrE/site/?key=statement




მაგალითები

შესატანი მონაცემები
42 23 6 20 25 14 27 30 7 დაკოპირება
გამოსატანი მონაცემები
4 დაკოპირება

შენიშვნა

მაგალითის განმარტება : ბაიტეზარს შეუძლია გამოიყენოს ტაქსები ნომრით 4, 5, 1 და 2.