프로게이머 영식

영식이는 숌크래프트의 프로게이머이다. 최대 라이벌 민식이와의 승부를 앞두고, 제한된 시간 안에 가장 강한 유닛을 최대한 많이 생산하려고 한다.

숌크래프트에는 1번부터 N번까지 번호가 붙은 유닛이 있다. 게임은 1번 유닛 1마리만 가진 상태로 시작한다. 건물이 없기 때문에 유닛이 다음 번호의 유닛을 생산한다. 즉, i번 유닛은 i+1번 유닛을 만들 수 있다. 이 생산에는 Time[i]초가 걸리고 Cost[i]만큼의 자원이 필요하다. 생산을 시작한 유닛은 해당 생산이 끝난 뒤 다시 생산할 수 있으며, 서로 다른 유닛들의 생산은 동시에 진행될 수 있다.

번호가 큰 유닛은 번호가 작은 모든 유닛을 이긴다. 따라서 영식이는 싸움이 시작되기 전까지 N번 유닛을 가능한 한 많이 만들고 싶다. 싸움까지 남은 시간 T와 현재 가진 자원 C가 주어질 때, 만들 수 있는 N번 유닛의 최대 개수를 구하시오. 자원은 추가로 늘어나지 않으며, 명령을 내리는 데 걸리는 시간은 0초로 본다.

첫째 줄에 유닛의 개수 N이 주어진다. N은 300 이하의 자연수이다.

둘째 줄에 현재 자원 C와 남은 시간 T가 주어진다. C와 T는 300 이하의 자연수이다.

셋째 줄부터 N-1개의 줄에는 Cost[i]와 Time[i]가 차례로 주어진다. i번째 줄은 i번 유닛이 i+1번 유닛을 만드는 데 필요한 자원과 시간을 뜻한다.

만들 수 있는 N번 유닛의 최대 개수를 첫째 줄에 출력한다.