Цукеркоман

Андрій, як справжній цукеркоман, коли приходить в магазин купляє все, що бачить. А саме, у кожний свій візит він купляє цукерки з послідовними номерами від $l$ до $r$.

Завтра Андрій вирушає на дуже відповідальний захід — фінал ВЮДОІ, а тому хоче взяти з собою як можна більше цукерок. Він знає, що цукерка з номером $i$ важить $i$ грамів, а його рюкзак може витримувати вагу до $w$ грамів. Всього було $n$ візитів до магазину, в кожен з яких він може придбати цукерки з інтервалу $[l_i,r_i]$. Скажіть максимальну кількість цукерок, яку він може взяти з собою, якщо відомо, що він може брати не більше $i$ цукерок з номером $i$.

Input

Перший рядок містить два цілі числа $n$ ($1\le n\le 10^6$) та $w$ ($1\le w\le 10^{12}$) — кількість візитів до магазину та максимальна вага, яку може витримати рюкзак Андрія у грамах.

Наступні $n$ рядків містять кожен по два цілі числа $l_i$ та $r_i$ ($1\le l_i\le r_i\le 10^5$).

Output

Виведіть одне ціле число — відповідь на задачу.

Examples

Note

Пояснення до першого прикладу:

Список усіх цукерок, які купив Андрій — $[1,2,3,4,2,3,4,5]$.

Один з варіантів взяти $5$ цукерок — $[2,3,4,3,2]$.

Пояснення до другого прикладу:

Один з варіантів взяти $7$ цукерок буде наступним — $[1,2,2,3,3,4,5]$, сумарна вага буде 20 грамів.