J — Munkaállomások kiosztása

A képet a NASA készítette

Penelope egy nemrég kiépített szuperszámítógép adminisztrátori csapatának a tagja. A feladata, hogy kiossza a munkaállomásokat azoknak a kutatóknak, akik a számításaikat szeretnék lefuttatni a szuperszámítógépen.

Penelope meglehetősen lusta: nem szereti feloldani a gépek zárolását az érkező kutatóknak. Bár a gépeket távolról, az íróasztaláról is fel tudja oldani, úgy érzi, ez az alantas feladat nem felel meg a képesítésének. Ha úgy döntene, hogy figyelmen kívül hagyja a biztonsági előírásokat, akkor egyszerűen megkérhetné a kutatókat, hogy ne zárják le a munkaállomásukat a munkájuk végeztével, és akkor az újonnan érkező kutatókat olyan munkaállomásokhoz rendelhetné, amelyek már nincsenek használatban, de még nincsenek zárolva. Ezzel a módszerrel minden munkaállomást csak az első azt használó kutató számára kellene feloldania, és ez nagy előrelépést jelentene Penelope számára.

Sajnos azonban a nem használt munkaállomások automatikusan lezárják magukat, ha nem használják őket több, mint m percen keresztül. Miután egy munkaállomás lezárja magát, Penelopénak újra fel kell azt oldania a következő azt használó kutató számára. Ha adott az érkező és távozó kutatók pontos időbeosztása, meg tudnád-e mondani Penelopénak, hogy hány feloldástól szabadulhat meg, ha megkéri a kutatókat, hogy ne zárják le a munkaállomásukat távozáskor, és ha az érkező kutatóknak optimálisan osztja ki a munkaállomásokat? Feltételezheted, hogy mindig rendelkezésre áll elegendő számú munkaállomás.

A bemenet specifikációja

A bemenet az alábbi sorokból áll:

az első sorban két egész szám, n és m szerepel (1 ≤ n ≤ 300 000, 1 ≤ m ≤ 10⁸), ahol n a kutatók száma, m pedig az a percben mért idő, amennyi inaktivitás után a munkaállomások lezárják magukat;
a következő n sor mindegyike két egész számot tartalmaz: a-t és s-et (1 ≤ a, s ≤ 10⁸), amelyek egy olyan kutatót adnak meg, aki a perc után érkezik és pontosan s percig marad.