Cursuri

Călin, dornic să acumuleze cât mai multă informație, dorește să participe la $N$ cursuri, de la mai multe facultăți, care au loc la intervale de timp $[L,R]$. Din păcate pentru el, aceste cursuri se suprapun; din fericire, are niște prieteni apropiați care îl pot ajuta ducându-se și ei la cursuri și transmițându-i informația. Deoarece informația nu curge la fel în acest mod, Călin se mulțumește cu informația de la cel puțin $K$ dintre cursuri. Pentru că tot acest proces necesită concentrare, după ce fiecare persoană participă la un curs, acesta va lua o pauză de durată $T$ în care nu va mai putea participa la un alt curs.

De câți oameni este nevoie pentru a se afla informația de la minim $K$ cursuri? Se consideră că trebuie să se participe în intregime la fiecare curs, și că într-un moment de timp se admite ca o persoană să termine un curs/pauza luată, și să se ducă în același moment de timp la un alt curs.

Mai mult, pentru numărul minim de oameni determinați, care este pauza maximă pe care aceștia o pot lua fiecare?

Date de intrare

Pe prima linie se află $N$ - numărul de cursuri totale, $K$ - numărul minim de cursuri despre care dorim să aflăm informații și $T$ - pauza luată de fiecare. Pe fiecare din următoarele $N$ linii se va afla câte o pereche de numere $l \ r$ reprezentând momentul de început, respectiv de final al unui curs.

Date de ieșire

Se vor afișa numărul minim de oameni necesari, respectiv pauza maximă pe care aceștia o pot lua, sau $−1$ dacă aceasta poate fi oricât de mare.

Restricții și precizări

• $1 \leq K \leq N \leq 50 \ 000$
• $1 \leq l_i \leq r_i ≤ 10^9$
• $0 \leq T \leq 10^9$
• Pentru fiecare subtask, se acordă $75 \%$ din punctaj pentru numărul minim de persoane și, dacă numărul minim este determinat corect, încă 25% din punctaj pentru pauza maximă.

Exemplul 1

cursuri.in

3 2 3
1 4
4 6
6 7

cursuri.out

2 -1

Explicație

Pentru primul exemplu, avem nevoie de $2$ oameni care vor lua o pauză de durată $3$ pentru a participa la $2$ dintre cursuri. O persoană va participa la cursul de la $[1, 4]$, iar cealaltă la cursul de la $[4, 6]$. Aceștia pot lua o pauză indefinit de lungă.

Exemplul 2

cursuri.in

3 2 0
1 4
4 6
6 7

cursuri.out

1 2