Rezolvare PBinfo #4220

Cerința

Vrei să călătorești n kilometri din orașul A în orașul B cu o mașină care are un rezervor de combustibil care poate asigura un număr de m kilometri. Între cele două orașe sunt amplasate stații de alimentare cu combustibil. Mașina pleacă din orașul A cu rezervorul plin. Vrei să știi numărul minim de alimentări necesare parcurgerii distanței între cele două orașe sau dacă nu se poate parcurge distanța din cauza alimentării (ai o mașină electrică și nu prea sunt stații electrice de alimentare :) )

Date de intrare

Fișierul de intrare masina.in conține pe prima linie numărul n care reprezintă distanța dintre orașele A și B, pe a doua linie numărul m care reprezintă numărul de kilometri care pot fi parcurși cu o alimentare. Pe a treia linie o valoare k reprezentând numărul de stații de alimentare. Pe a patra linie se află un șir de k valori: d[1], d[2], d[3], …, d[k] reprezentând distanța dintre fiecare stație de alimentare și orașul de pornire A.

Date de ieșire

Fișierul de ieșire masina.out va conține pe prima linie numărul a, reprezentând numărul minim de alimentări dintre cele două orașe sau -1 dacă nu se poate parcurge distanța .

Restricții și precizări

• 1 ≤ n ≤ 205.000
• 1 ≤ m ≤ 400
• 1 ≤ k ≤ 1000
• 1 ≤ d[i] ≤ n

Exemplu:

masina.in

800
300
4
200 475 550 750

masina.out

3

Explicație

Sunt necesare 3 opriri: la stațiile 1, 2, 4.