У Иай есть $n$ единиц снаряжения, каждое из которых изначально находится на $0$-м уровне. Каждую единицу снаряжения можно улучшить ровно два раза: для улучшения $i$-го снаряжения с $0$-го до $1$-го уровня требуется $w_{i,1}$ золотых монет, а с $1$-го до $2$-го уровня — $w_{i,2}$ золотых монет.

Иай хочет узнать, какое минимальное количество золотых монет ей потребуется потратить, чтобы выполнить в сумме $m$ улучшений снаряжения.

Входные данные

В первой строке заданы два целых положительных числа $n$ и $m$, обозначающие общее количество снаряжения и необходимое количество улучшений.

Далее следуют $n$ строк, в каждой из которых записаны два целых положительных числа $w_{i, 1}$ и $w_{i, 2}$, обозначающие стоимость первого и второго улучшений для $i$-го снаряжения соответственно.

Выходные данные

Выведите одно целое число — минимальное количество золотых монет, которое необходимо потратить.

Примеры

Пример 1

Входные данные

5 7
1 3
2 1
2 5
4 2
1 1

Выходные данные

11

Примечание

Выбранные улучшения:

• Первое снаряжение: 2 уровня.
• Второе снаряжение: 2 уровня.
• Третье снаряжение: 1 уровень.
• Пятое снаряжение: 2 уровня.

Общая стоимость составляет $(1+3)+(2+1)+2+(1+1)=11$ монет.

Пример 2

См. файлы ex_2.in и ex_2.ans в директории загрузки.

Подзадачи

Для $100\%$ данных гарантируется, что $1\le n \le 5 \times 10^{5}, 1\le m\le 2n, w_{i,j} \le 10^{9}$.

Особое свойство A: для всех $i$ выполняется $w_{i,1} \ge w_{i,2}$.

Особое свойство B: для всех $i$ выполняется $w_{i,1} \le w_{i,2}$.