당근 클릭 게임

면접 대비

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

요약

N개의 속도 효과마다 비용 A_i와 속도 증가량 B_i가 주어질 때, K초 동안 클릭과 구매를 섞어 얻을 수 있는 당근의 최댓값을 구합니다.

문제

에릭은 방학 동안 너무 심심한 나머지, 당근 클릭 게임이라는 게임을 직접 만들어서 플레이하기로 했다.

게임을 시작할 때 에릭은 당근을 0개 가지고 있고, $s$ 는 1이다.

매초 다음 두 가지 행동 중 하나를 할 수 있다.

마우스를 클릭하고 당근을 $s$ 개 얻는다.
정수 $i$ ( $1 \le i \le N$ )를 고르고, 당근 $A_i$ 개를 지불하여 $i$ 번째 스피드 효과를 구매한다. 구매 직후 $s$ 가 $B_i$ 만큼 증가한다. (이전에 구매한 스피드 효과를 다시 구매하는 것도 가능하다.)

게임을 개발하느라 에너지를 모두 소모해 버린 에릭을 위해, 게임을 $K$ 초 플레이한 후 당근을 최대 몇 개까지 가지고 있을 수 있는지 구하자.

첫 번째 줄에 두 정수 $N$ , $K$ 가 공백으로 구분되어 주어진다.

다음 $N$ 개의 줄 중 $i$ 번째 줄에는 두 정수 $A_i$ , $B_i$ 가 공백으로 구분되어 주어진다.

에릭이 게임을 $K$ 초 플레이한 후 가지고 있을 수 있는 당근의 최대 개수를 출력한다.