cinador   3년 전

문제

N종류의 게임이 있다. 오늘부터 D일 동안 하루에 한 가지의 게임을 골라 플레이 하려고 한다. 하나의 게임을 여러 날 플레이 해도 되고, 한 번도 플레이 하지 않는 게임이 있어도 된다.

게임을 플레이 하게 되면, 플레이 한 게임이 그 날에 가지고 있는 즐거움을 얻게 된다. i번째 게임의 즐거움의 초기값은 Ai 이다. 어떤 날에 i번째 게임을 플레이 하게 되면, 다음 날의 이 게임의 즐거움은 Bi 만큼 감소한다. 반대로, 어떤 날에 i번째 게임을 플레이 하지 않는다면, 다음 날의 이 게임의 즐거움은 초기값인 Ai를 넘지 않는 범위에서 Bi 만큼 회복한다. 즉, 오늘 i번째 게임의 즐거움을 x라 하면, 내일 이 게임의 즐거움은, 오늘 이 게임을 플레이 한다면 x - Bi, 오늘 이 게임을 플레이 하지 않는다면 min(x + Bi, Ai) 이 된다.

매일 플레이 할 게임을 적절하게 골라 D일 동안 지낼 때, D일 동안 얻게 되는 즐거움의 총합의 최댓값을 구하여라.

ㅤ

입력

입력은 최대 50개의 테스트 케이스로 이루어져 있으며, 각 테스트 케이스는 다음과 같은 형식을 갖는다.

 N D

 A1 B1

 ...

 AN BN 

첫 번째 줄에는 정수 N과 정수 D가 주어진다. N은 게임의 종류 수를 나타내며,1 ≤ N ≤ 100,000 을 만족한다. D는 게임을 플레이 할 기간을 나타내며, 1 ≤ D ≤ 100,000 을 만족한다.

다음 N줄에는 N종류의 게임의 정보가 주어진다. N개의 줄 중 i번째 줄에는 정수 Ai 와 정수 Bi 가 주어진다. Ai 는 i번째 게임의 즐거움의 초기값을 나타내며, 1 ≤ Ai ≤ 100,000 을 만족한다. Bi 는 i번째 게임을 플레이 했을 때의 즐거움의 감소량을 나타내며, 1 ≤ Bi ≤ 100,000 을 만족한다.

입력의 마지막에는 두 개의 0이 주어진다. 

ㅤ

출력

각 테스트 케이스에 대해, 답을 한 줄에 하나씩 출력한다.

ㅤ

ㅤ

힌트

첫 번째 테스트 케이스에서, 게임 1, 게임 2, 게임 1의 순서로 플레이 하게 되면, 즐거움의 총합은 10 + 1 + 10 = 21 이 된다.

두 번째 테스트 케이스에서, 게임 1을 3일 연속으로 플레이 할 수 밖에 없으므로, 즐거움의 총합은 10 + 9 + 8 = 27 이 된다.

댓글을 작성하려면 로그인해야 합니다.