6. Odďaľovanie roboty

Bob by mal pracovať na dizertačnej práci, ale veľmi sa mu nechce. Keďže do ukončenia PhD zostáva ešte čas, Bob preferuje iné činnosti ako napríklad hranie frisbee.

Každý Bobov rok vyzerá tak, že mu školiteľ dá \(n\) rôznych problémov, ktoré by mal vyriešiť v rámci dizertačnej práce. Aby školiteľ Boba motivoval,¹ každá úloha má svoj termín, dokedy ju má urobiť. Bob sa ale statočne bráni a má celkom jednoduchú stratégiu. Najprv sa chce čo najdlhšie flákať (venovať sa iným činnostiam ako dizertačke), a až potom začne robiť na úlohách.

Navyše sa mu podarilo zistiť, že jeho školiteľ je príliš mäkký. Bob si tak môže beztrestne dovoliť nespraviť najviac \(k\) úloh. Ako najdlhšie sa môže Bob zo začiatku flákať pri takejto stratégii?

Úloha

Máme zadaných \(n\) úloh. Pre každú úlohu vieme, koľko času Bob potrebuje na to, aby ju splnil – \(t_i\) a dokedy ju má splniť – deadline \(d_i\). Vašou úlohou je zistiť, ako najdlhšie sa môže na začiatku flákať, pričom si môže dovoliť nespraviť najviac \(k\) úloh. Bob vie pracovať v jednom čase najviac na jednej úlohe. Keď Bob začne pracovať na úlohe, celú ju spraví naraz.

Formát vstupu

V prvom riadku sú dve celé čísla oddelené medzerou \(1 \leq n \leq 3000\) a \(0 \leq k < n\). V ďalších \(n\) riadkoch sa nachádzajú dvojice celých čísel oddelených medzerou \(1 \leq d_i \leq 10^9\) a \(1 \leq t_i \leq \min(d_i, 10^6)\), pričom \(d_i\) je deadline do ktorého treba splniť \(i\)-tu úlohu a na jej dokončenie treba \(t_i\) času.

V jednej sade vstupov zo štyroch bude platiť \(k = 0\).

Formát výstupu

Vypíšte jedno nezáporné celé číslo – ako dlho sa môže Bob na začiatku flákať, aby nestihol najviac \(k\) termínov. Bob sa chce najskôr čo najdlhšie flákať, a potom, až keď je to nevyhnutné, začne robiť. Ak sa úloha nedá splniť, vypíšte Neda sa to stihnut.

Príklad

Input:

2 0
10 5
7 1

Output:

4

Bob začne s druhým termínom v čase 4. Dokončí ho v čase 5, a potom pracuje na prvom, ktorý dokončí v čase 10.

Input:

3 1
10 3
8 2
6 2

Output:

5

Bob si povie, že zmešká tretí termín a začne druhým v čase 5 a dokončí ho v čase 7. Potom začne robiť na prvej úlohe. Môžete si všimnúť, že ak by Bob nespravil prvú úlohu, mal by celkovo viac voľného času, lenže jemu ide len o to, aby prácu čo najviac oddialil.

Input:

2 0
10 10
2 2

Output:

Neda sa to stihnut.