시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB1523318.750%

문제

영식이는 숌크래프트의 프로게이머이다. 영식이는 자신의 최대 라이벌 민식이와의 피할 수 없는 승부를 대비하기 위해서 숌크래프트를 준비하기로 했다.

숌크래프트에는 유닛이 총 N개 존재하는데, 각각의 유닛은 1번부터 N번까지 차례대로 번호가 매겨져 있다. 게임의 시작은 유닛 1번 1대만 주어지고 시작한다. 이 게임에는 건물이란 개념이 없기 때문에, 유닛이 유닛을 생산한다. 유닛 1번이 유닛 2번은 만들 수 있고, 유닛 2번이 유닛 3번을 만들 수 있고, ... 유닛 i번이 유닛 i+1번을 만드는 형식이다. 이 게임에도 자원이 존재하는데, 유닛 1번이 유닛 2번을 만들 때 걸리는 시간을 Time[1]이라고 하고, 그때 드는 자원을 Cost[1]이라고 한다. 한마디로 유닛 i번이 유닛 i+1번을 만드는데 걸리는 시간은 Time[i]이고, 필요한 자원은 Cost[i]이다. 이 게임은 독특해서 유닛 번호가 높은 유닛이 유닛 번호가 낮은 유닛을 모두 이긴다. (물량 무시) 따라서 영식이는 유닛 번호 N번을 최대한 많이 뽑으려고 한다.

게임은 시작됐다. 숌크래프트에서는 시간을 정해놓고 그 시간부터 싸움을 시작한다. 민식이와의 피할 수 없는 승부까지 남은 시간 T와 현재 영식이의 자원 C가 주어졌을 때, 영식이가 뽑을 수 있는 유닛 번호 N번의 최대개수를 구하는 프로그램을 작성하시오. 자원은 더 이상 늘어나지 않는다. 주어진 자원만 쓸 수 있다. 또, 모든 활동은 동시에 일어나며, 영식이가 유닛을 선택해서 다른 유닛을 만드는 버튼을 누르는데 걸리는 시간은 0초이다. (영식이가 게임 명령을 내리는 시간은 생각하지 않는다.)

예를 들어, 유닛의 개수가 3개이고, 남은 시간이 3이고, 현재 자원이 5이고, 유닛1이 유닛2를 만드는 시간과 자원이 모두 1들고, 유닛2와 유닛3을 만드는데 시간과 자원이 모두 1이 들면, 게임이 시작하자마자 유닛1이 유닛2를 만들면, 시간1이 됐을 때, 현재 유닛은 유닛1 1마리와 유닛2 1마리이다. 시간1일 때, 유닛1이 유닛2를 만들고, 유닛2가 유닛3을 만들면, 시간2가 됐을 때 총 유닛은 유닛1 1마리, 유닛2 2마리, 유닛3 1마리이다. 여기서 유닛2 2마리가 각각 유닛3를 한 마리씩 만들면, 시간3이 되었을 때는, 유닛1 1마리, 유닛2 2마리, 유닛3 3마리가 되어, 정답은 3이 된다.

입력

첫째 줄에 유닛의 개수 N이 주어진다. 유닛의 개수는 300보다 작거나 같은 자연수이다. 둘째 줄에 현재 영식이의 자원 C와 현재 남은 시간 T가 주어진다. C와 T는 300보다 작거나 같은 자연수이다. 셋째 줄부터 N-1개의 줄에 한 줄에 하나씩 Cost[i]와 Time[i]가 들어온다. 입력은 유닛 1번이 유닛 2번을 만드는데 드는 비용과 걸리는 시간, 유닛 2번이 유닛 3번을 만드는데 드는 비용과 걸리는 시간과 같은 순서대로 들어온다.

출력

첫째 줄에 영식이가 최대로 뽑을 수 있는 유닛 N번의 개수를 출력한다.

예제 입력 1

3
100 27
1 3
1 12

예제 출력 1

6

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: kipa00