Андрій, як справжній цукеркоман, коли приходить в магазин купляє все, що бачить. А саме, у кожний свій візит він купляє цукерки з послідовними номерами від l до r.
Завтра Андрій вирушає на дуже відповідальний захід — фінал ВЮДОІ, а тому хоче взяти з собою як можна більше цукерок. Він знає, що цукерка з номером i важить i грамів, а його рюкзак може витримувати вагу до w грамів. Всього було n візитів до магазину, в кожен з яких він може придбати цукерки з інтервалу [li,ri]. Скажіть максимальну кількість цукерок, яку він може взяти з собою, якщо відомо, що він може брати не більше i цукерок з номером i.
Перший рядок містить два цілі числа n (1≤n≤106) та w (1≤w≤1012) — кількість візитів до магазину та максимальна вага, яку може витримати рюкзак Андрія у грамах.
Наступні n рядків містять кожен по два цілі числа li та ri (1≤li≤ri≤105).
Виведіть одне ціле число — відповідь на задачу.
Пояснення до першого прикладу:
Список усіх цукерок, які купив Андрій — [1,2,3,4,2,3,4,5].
Один з варіантів взяти 5 цукерок — [2,3,4,3,2].
Пояснення до другого прикладу:
Один з варіантів взяти 7 цукерок буде наступним — [1,2,2,3,3,4,5], сумарна вага буде 20 грамів.