짐 싸기

면접 대비

시간 제한2초메모리 제한1024 MB

요약

각 종류의 짐을 한 개 더 넣을 때마다 얻는 가치가 A_i만큼 줄어듭니다. 가방에 최대 K개를 넣을 때 얻을 수 있는 가치의 최댓값을 구합니다.

문제

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

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

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