ŠIOM — Autobusas

Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_2018_1et_autobusas_jau.in

Rezultatų failas: lmio_2018_1et_autobusas_jau.out

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Autobusas

Autubuso maršrutą sudaro N stotelių. Į pirmą stotelę autobusas atvažiuoja tiesiai iš parko, todėl jis visuomet būna tuščias. Toliau kiekvienoje stotelėje į autobusą įlipa ir išlipa kažkiek keleivių.

Keleiviai mėgsta sėdėti, tad jeigu autobuse yra laisvų sėdimų vietų – keleiviai atsisės, o stovės tik tada, kai nebus nė vienos laisvos sėdimos vietos. Iš viso autobuse yra K sėdimų vietų.

Užduotis

Jums žinoma, kiek kiekvienoje stotelėje įlips ir išlips keleivių. Raskite, kiek daugiausiai keleivių vienu metu turės stovėti autobuse.

Pradiniai duomenys

Pirmoje eilutėje pateikti du sveikieji skaičiai $N$ ir $K$ . $N$ yra stotelių skaičius autobuso maršrute, o $K$ – sėdimų vietų skaičius autobuse.

Tolesnėse $N$ eilučių pateikta po du skaičius $a_i$ ir $b_i$ . $a_i$ – tai stotelėje įlipsiančių keleivių skaičius, o $b_i$ – išlipsiančių keleivių skaičius.

Rezultatai

Išveskite vieną sveikąjį skaičių – kiek daugiausiai keleivių turės stovėti autobuse vienu metu.

Pavyzdžiai

Pradiniai duomenys	Rezultatai	Paaiškinimas
4 10 5 0 5 2 10 5 0 13	3	Tarp trečios ir ketvirtos stotelės 10 keleivių sėdės, o 3 stovės.
5 12 7 0 4 3 8 4 5 5 0 12	0	Šiuo atveju visi keleiviai ras sėdimą vietą.

Ribojimai