Андр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в.