Цукеркоман#11360
Андрій, як справжній цукеркоман, коли приходить в магазин купляє все, що бачить. А саме, у кожний свій візит він купляє цукерки з послідовними номерами від до .
Завтра Андрій вирушає на дуже відповідальний захід — фінал ВЮДОІ, а тому хоче взяти з собою як можна більше цукерок. Він знає, що цукерка з номером важить грамів, а його рюкзак може витримувати вагу до грамів. Всього було візитів до магазину, в кожен з яких він може придбати цукерки з інтервалу [l_i, r_i]. Скажіть максимальну кількість цукерок, яку він може взяти з собою, якщо відомо, що він може брати не більше цукерок з номером .
Перший рядок містить два цілі числа (1 \le n \le 10^6) та (1 \le w \le 10^{12}) — кількість візитів до магазину та максимальна вага, яку може витримати рюкзак Андрія у грамах.
Наступні рядків містять кожен по два цілі числа l_i та r_i (1 \le l_i \le r_i \le 10^5).
Виведіть одне ціле число — відповідь на задачу.
Example 1
Example 2
Пояснення до першого прикладу:
Список усіх цукерок, які купив Андрій — [1,2,3,4,2,3,4,5].
Один з варіантів взяти цукерок — [2,3,4,3,2].
Пояснення до другого прикладу:
Один з варіантів взяти цукерок буде наступним — [1,2,2,3,3,4,5], сумарна вага буде грамів.