7279번 - 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 nei vienos laisvos sėdimos vietos. Iš viso autobuse yra K sėdimų vietų.

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

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.

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

• 2 ≤ N ≤ 1 000
• 0 ≤ a_i, b_i, K ≤ 1 000