여러분류의 문제가 있고 각 분류에는 무한 개의 문제가 있고 같은 분류의 문제는 같은 시간과 같은 점수를 얻게 된다.

주어진 대회시간 내에 어떤 분류의 문제를 몇 문제 선택하는게 최선의 점수를 얻게 되는 가를 알려주는 프로그램을 작성하는 것이 문제이다. 경우에 따라 어떤 분류의 문제는 선택되지 않 을 수 있다.

입력형식

다음 N 줄에는 한 줄에 각 문제 분류당 점수와 이 분류의 문제를 푸는 경우의 시간이 입력된다. 점수와 시간은 1 이상 10,000 이하이다.

출력 형식

입출력 예

입력

300 4
100 60
250 120
120 100
35 20

출력

605

보기의 답은 2 번분류에서 2 문제, 4 번 분류에서 3 문제를 선택하는 경우가 최대이다.

출처: usaco