这次的月考LF_KZOI考的很烂，于是决定总结自己为什么会考得这么烂。当然，学习不用功是一个原因，但是应试策略 
上也存在一点问题。他几次出现时间不够的情况。于是他决定要计算一下，在最好的应试策略下，他能考到的分数S。因为他是 
参加信息学奥赛的。这个问题过于简单。于是他决定考验一下他的师妹，师弟。 
他为每道题目从前往后编号为1..n,然后为每道题目设定了一个时间Ti还有解题能得到的分数Si。显然考试时有限定时 
间的。假定限定时间为T。 
因为LF_KZOI做题目比较有个性。绝对不会等到后面的题目做好了再来做前面的题目。而且每道题目要么不做，做就一 
定要做好。 
要求在最好的应试策略下它能得到几分。

Input 

第一行一个整数n，表示总共有n道题目。第二行到第n+1行，每行有两个整数Ti,Si，表示的意义和题目中描述的一样最后一个正整数T，表示总共的时间

Output 

一行。包含一个整数,既最大得分。

Sample Input 


3
10 20
40 30
20 20
40

Sample Output 


40