Županijsko natjecanje / Osnovna škola (8. razred) 2022 - 1. zadatak

Lovro i Fran vraćaju se doma nakon napornog dana u školi. Kao što to i inače biva, pred nosom im je pobjegla poznata linija 146 i sada ju moraju tužno promatrati kako prolazi sljedećih N stanica. Kako bi si skratili vrijeme, počeli su razmišljati o broju putnika u autobusu.

Naime, opće je poznato da se u ovom autobusu u svakom trenutku, suprotno zakonima fizike, može nalaziti najviše L putnika. Lovro i Fran su svojim oštrim vidom zamijetili da je na i-toj stanici prvo iz autobusa izašlo Ai putnika, a zatim ušlo njih Bi.

Sada ih zanima koliko se najmanje i najviše putnika može nalaziti u autobusu nakon što je prošao svih N stanica. Naravno, u autobusu se ni u jednom trenutku nije nalazio negativan broj putnika, niti je u njemu bilo više od L putnika.

Ulazni podaci

U prvom retku su prirodni brojevi N (1 ≤ N ≤ 100000) i L (1 ≤ L ≤ 100000), brojevi iz teksta zadatka.

U sljedećih N redaka nalaze se brojevi Ai (1 ≤ Ai ≤ 100000) te Bi (1 ≤ Bi ≤ 100000), brojevi iz teksta zadatka.

Izlazni podaci

U prvi redak ispiši koliko je najmanje i najviše moguće putnika u autobusu nakon što je prošao zadanih N stanica.

Probni primjeri

Ulaz

1 20
5 7

Izlaz

7 20

Opis prvog probnog primjera:

Na prvoj i jedinoj stanici je ušlo 7 putnika stoga se u autobusu mora nalaziti barem sedam putnika. Prije prve stanice moglo se nalaziti između 5 (jer ih je toliko izašlo) i 18 (kada pet izađe, da sedam može ući) putnika, stoga je na kraju svaki broj između 7 i 20 moguć.

Ulaz

3 9
1 3
1 2
3 1

Izlaz

2 7

Opis drugog probnog primjera:

Nalazi li se u autobusu nakon zadnje stanice više od 7 putnika, to bi značilo da ih je prije treće stanice u busu moralo biti više od 9. Nalazi li se manje od 2 putnika, značilo bi da se nakon izlaska putnika na prvoj stanici u autobusu nalazio negativan broj putnika.

Ulaz

5 15
3 7
3 1
5 1
2 7
6 6

Izlaz

7 14