Yi Ai ma obecnie $n$ elementów wyposażenia, z których każdy znajduje się w stanie początkowym, zwanym poziomem $0$. Każdy element wyposażenia można ulepszyć dokładnie dwa razy: ulepszenie $i$-tego elementu z poziomu $0$ na poziom $1$ kosztuje $w_{i,1}$ sztuk złota, a z poziomu $1$ na poziom $2$ kosztuje $w_{i,2}$ sztuk złota.

Yi Ai chce wiedzieć, jaki jest minimalny koszt w sztukach złota, aby wykonać łącznie $m$ ulepszeń wyposażenia.

Wejście

Dane wczytywane są ze standardowego wejścia.

Pierwsza linia zawiera dwie dodatnie liczby całkowite $n, m$, oznaczające łączną liczbę elementów wyposażenia oraz liczbę wymaganych ulepszeń.

Następnie podano $n$ linii, z których każda zawiera dwie dodatnie liczby całkowite $w_{i, 1}, w_{i, 2}$, oznaczające koszty odpowiednio pierwszego i drugiego ulepszenia $i$-tego elementu wyposażenia.

Wyjście

Wyprowadź wynik na standardowe wyjście.

Wyprowadź jedną dodatnią liczbę całkowitą oznaczającą minimalny koszt w sztukach złota.

Przykład

Wejście 1

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

Wyjście 1

11

Uwagi

Wybrane ulepszenia:

• Pierwszy element wyposażenia ulepszony do poziomu 2.
• Drugi element wyposażenia ulepszony do poziomu 2.
• Trzeci element wyposażenia ulepszony do poziomu 1.
• Piąty element wyposażenia ulepszony do poziomu 2.

Łączny koszt wynosi $(1+3)+(2+1)+2+(1+1)=11$ sztuk złota.

Przykład 2

Zobacz pliki ex_2.in oraz ex_2.ans w katalogu do pobrania.

Podzadania

Dla $100\%$ danych wejściowych zachodzą warunki: $1\le n \le 5 \times 10^{5}, 1\le m\le 2n, w_{i,j} \le 10^{9}$.

Własność specjalna A: dla wszystkich $i$ zachodzi $w_{i,1} \ge w_{i,2}$.

Własność specjalna B: dla wszystkich $i$ zachodzi $w_{i,1} \le w_{i,2}$.