Saman bayramı
Fermer Con öz inəkləri üçün ləzzətli yemək hazırlayır. Onun anbarında n ot tayası var. i-ci taya müəyyən bir dad f[i] (1 ≤ f[i] ≤ 10^9) və müəyyən bir ədviyyat s[i] (1 ≤ s[i] ≤ 10^9) malikdir.
Yemək bir və ya daha çox ardıcıl ot tayasını əhatə edən fasiləsiz bir intervaldan ibarət olacaq (onların sırasını dəyişmək olmaz). Yeməyin ümumi dadı intervaldakı dadların cəminə bərabərdir. Yeməyin ümumi ədviyyatı intervaldakı ədviyyatların maksimumuna bərabərdir.
Con dadın ən azı m olması üçün əldə edilə biləcək minimum ədviyyatı müəyyən etmək istəyir.
Giriş məlumatları
Birinci sətir n (1 ≤ n ≤ 10^5) və m (1 ≤ m ≤ 10^18) tam ədədlərini ehtiva edir - ot tayalarının sayı və çatılması lazım olan minimum dad, müvafiq olaraq. Növbəti n sətir n ot tayasını təsvir edir, hər sətirdə bir cüt ədəd - birinci dad f, ikinci isə ədviyyat s.
Çıxış məlumatları
Minimum ədviyyatı çıxarın ki, dadın minimum tələbi yerinə yetirilsin. Həllin mövcudluğu təmin edilir.