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

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

Скажiть максимальну кiлькiсть цукерок, яку вiн може взяти з собою, якщо вiдомо, що вiн може брати не бiльше ~i~ цукерок з номером ~i~.

Формат вхiдних даних

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

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

Формат вихiдних даних

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

Приклад вхідних даних

3 14 
1 4
2 3 
4 5

Приклад вихідних даних

5

Приклад вхідних даних

3 20
1 10
1 10
1 10

Приклад вихідних даних

7

Зауваження

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

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

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

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

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