32956번 - 짐 싸기

문제

$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$)

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

출력

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

제한

힌트