Problem D
Cloud Conundrum

Pixabay, cc0

Grovt förenklat så skulle man kunna säga mera jobb mera pengar. När man ändå gör grova
förenklingar så får man ju passa på att göra några till att säga att varje server i molnet kan ta ett jobb åt gången. Givetvis är hela principen med moln också beroende av att kunder lägger upp jobb som de vill ska genomföras i molnet.

Ett jobb består av en starttid si i sekunder efter en starttid $t_0=0$ när jobbet kommer läggas upp och ett tal li som representerar längden på jobbet också i sekunder. Det spelar ingen roll att ett arbete går över flera dagar utan uttrycker allt i sekunder efter t0. Ett antal kunder har nu lagt upp flera jobb men det är ingen som har tänkt på att kolla om man kan utföra alla beställda jobb (moln är ju jättestora, borde ju inte vara ett problem). Kunderna vill såklart inte ändra på sina jobb så det innebär att om det inte finns en server som kan börja arbeta på ett jobb på en gång kommer kunden hitta någon annan som kan utföra arbetet och ta tillbaka jobbet. Samtidigt vill man inte behöva använda fler servrar än nödvändigt, man tänker sig att det kanske ändå är mest värt att släppa några jobb om man inte behöver använda lika många servrar.

Nu vill man ha din hjälp att räkna ut hur många servrar man minimalt behöver för att serva $k$ antal jobb givet att servrarna har noll ställtid efter ett genomfört jobb. Dvs om ett jobb blir färdigt vid en tidpunkt $t_{end}$ kan nästa jobb börja om $\; t_{next} \geq t_{end}$

Indata

En rad med de två talen $n$ och $k$, det totala antalet arbeten och det antal jobb man minst vill utföra. Följande $n$ rader, två tal $s_ i$ och $l_ i$ som står för starttiden och längden för jobb $i$

$0 \leq k \leq n \leq 50000$
$0 \leq s_ i \leq 10^9$ $1 \leq l_ i \leq 10^9$

Utdata

Utdata är ett tal, det minimala antalet servar som behövs för att utföra tillräckligt många jobb.

7 5
10 5
2 8
6 13
8 2
5 5
1 6
2 10

3