짐 싸기

$N$ 종류의 짐과 최대 $K$개의 짐을 담을 수 있는 배낭이 있다. 각 짐의 가치를 표현하는 정수 배열 $A$와 $B$가 주어진다.

종류가 $i$인 짐을 $X\_i$개 고른 상태에서, 종류가 $i$인 짐 하나를 더 고르면 $B\_i - A\_i X\_i$만큼의 가치를 추가로 얻는다.

각 종류의 짐이 무한히 존재할 때, 얻을 수 있는 가치 합의 최댓값은 얼마인가?

첫 번째 줄에 $N$, $K$가 차례대로 주어진다. ($1 \le N \le 10^6;$ $1 \le K \le 10^9$)

두 번째 줄부터 $N$개의 줄에 걸쳐 $A\_i$, $B\_i$가 순서대로 주어진다. ($1 \le A\_i, B\_i \le 10^9$)

입력으로 주어지는 모든 수는 정수이다.

첫 번째 줄에 답을 출력한다.