Fişierul intrare/ieşire:licenta.in, licenta.outSursăFMI No Stress 6
AutorAlex PalcuieAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.3 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Licenta

Ajunsă în ultimul an de facultate, Mihaela se hotărăşte să îşi termine lucrarea de licenţă intitulată 'Polinomul minimal a unei rădăcini de ordin O într-o extensie algebrică de grad G'. Fiindcă in lucrarea ei a obţinut rezultate legate de existenţa marţienilor, aceasta doreşte să se întâlnească cu îndrumătorul ei, decanul.

Din păcate, timpul nu e de partea ei. Mihaela are la dispoziţie o mulţime de intervale S de dimensiune N la care poate veni în facultate.
Decanul este o persoană foarte ocupată, precum Mihaela, are la îndemână o mulţime de intervale T de dimensiune M în care este la biroul său.

Mihaela are nevoie de exact K minute pentru a explica ideile prezente în lucrarea ei indrumătorului. Pentru că eroina lucrează la conjectura P=NP vă roagă să găsiţi un interval de timp de fix K secunde astfel încât ea să fie la facultate iar profesorul ei îndrumător prezent în birou.

În caz că există mai multe soluţii de forma [X, Y], ea doreşte să afişaţi intervalul cu X minim. Dacă nu există o soluţie atunci afişaţi -1 pe prima linie.

Date de intrare

Fişierul de intrare licenta.in conţine pe prima linie numărul natural K specificat în enunţ. Pe a doua linie este un singur număr natural N reprezentând dimensiunea mulţimei S.
Următoarele N linii conţin câte 2 numere naturale separate prin câte un spaţiu: XS[i], YS[i] specificând intervalele de minute în care Mihaela este la facultate. Intervalele sunt disjuncte două câte două.

Următoarea linie conţine numărul natural M.
Următoarele M linii conţin câte 2 numere naturale separate prin câte un spaţiu: XT[j], YT[j] specificând intervalele de minute în care profesorul este la biroul său. Intervalele sunt disjuncte două câte două.

Date de ieşire

Prima linie conţine 2 numere naturale separate prin câte un spaţiu X Y, reprezentând intervalul de timp în care Mihaela se întâlneşte cu Decanul.

Restricţii

  • 1 ≤ K < 109
  • 1 ≤ N ≤ 105
  • 0 ≤ XS[i] < YS[i] < 109 oricare 1 ≤ i ≤ N
  • 1 ≤ M ≤ 105
  • 0 ≤ XT[j] < YT[j] < 109 oricare 1 ≤ j ≤ M
  • Pentru 40 de puncte 1 <= N * M <= 5 * 106
  • Pentru a lua 100 de puncte, you need to do it for the watch.

Exemplu

licenta.inlicenta.out
4
2
1 10
11 13
2
2 4
5 12
5 9

Explicaţie

Mihaela poate să ajungă la facultate în intervalele [1, 10]; [11, 13].
Decanul este în biroul său în intervalele [2, 4]; [5 12].

Se observă că dacă Miruna se întâlneşte începând cu minutul 5, aceasta reuşeşte să îi explice întreaga lucrare de licenţă timp de 4 minute. Ca urmare, soluţia este intervalul [5, 9].

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?