Fișierul intrare/ieșire broasca2.in, broasca2.out Sursă Concurs admitere clasa a 10-a
Autor Teodor Plop Adăugată de avatar teodor94 Teodor Plop teodor94
Timp de execuție pe test 1 sec Limită de memorie 5120 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Broasca2 (clasa a 10-a)

Haideți să discutăm despre celebrul lac Lixi. Câteva informații interesante despre acesta:

  • Distanța între malul de vest și malul de est al acestuia este de exact D metri.
  • Pe suprafața acestuia cad N frunze, fiecare frunză i căzând la timpul t[i] la exact p[i] metri distanță față de malul din partea de vest.
  • Există o legendă care spune că în jurul lacului se află o broscuță pe nume Bixi. Aceasta poate executa sărituri pe o distanță de maxim K metri.
  • Această broscuță legendară poate performa săriturile instant, în timp 0. Altfel nu ar mai fi chiar atât de legendară.

Suficiente informații pentru astăzi... Să trecem direct la problemă. Broscuța Bixi este reală și se află pe malul de vest al lacului, la distanță de exact 0 metri față de acesta. Ea dorește să ajungă pe malul de est (aflat la distanță de exact D metri față de malul de vest), sărind doar pe frunze.

Cerință

Să se spună dacă broscuța Bixi poate traversa lacul și în cazul în care poate, care este timpul minim în care acest lucru devine posibil.

Date de intrare

Fișierul de intrare broasca2.in conține pe prima linie numerele D, K și N, separate între ele prin câte un spațiu. Pe fiecare din următoarele N linii se găsesc câte două numere naturale, t[i] și p[i], având semnificația din enunț.

Date de ieșire

Fișierul de ieșire broasca2.out va conține o singură valoare. În cazul în care răspunsul este pozitiv, în fișier se va găsi un singur număr natural, reprezentând timpul minim în care broscuța poate traversa lacul. În cazul în care răspunsul este negativ, se va afișa -1.

Restricții

  • 1 ≤ D ≤ 100.000.000
  • 1 ≤ K ≤ 1.000
  • D / K ≤ 100.000
  • 1 ≤ N ≤ 500.000
  • 1 ≤ t[i] ≤ 1.000, 1 ≤ i ≤ N
  • 1 ≤ p[i] < D, 1 ≤ i ≤ N
  • Frunzele sunt date în ordinea cronologică în care acestea pică pe lac.
  • Frunzele nu cunosc conceptul de distanțare socială. Putem avea mai multe frunze în același loc.

Exemplu

broasca2.in broasca2.out Explicație
10 10 2
1 7
2 5
0
Distanța dintre maluri este 10, iar Bixi poate sări pe o distanță de maxim 10. Deci ea poate sări direct de pe malul de vest pe malul de est.
10 5 2
1 7
2 3
2
În prima secundă, avem o frunză pe poziția 7. Bixi rămâne pe malul de vest.
În cea de-a doua secundă, apare o frunză pe poziția 3. Bixi sare pe ea, apoi sare pe cea de pe poziția 7, apoi sare pe malul de est.
10 5 2
1 7
2 1
-1
În prima secundă, avem o frunză pe poziția 7. Bixi rămâne pe malul de vest.
În cea de-a doua secundă, apare o frunză pe poziția 1. Chiar dacă Bixi sare pe ea, nu are cum să ajungă pe celălalt mal.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii