Descr iption



　　现在大家正在为完成网络教室的题目而奋斗。你想获得更高的分数，但发现自己的效率有点儿低，于是请你写个程序计算一下：



　　假设一共有 n 个题目，每个题目 i 你都需要一个单位时间来完成。同时每个题目 i 都有一个完成期限 di 和相应的分数 pi 。这里的完成期限是指应在开始时间之后 di 个时间单位内（含di）完成，不能迟交。



　　所有题目同时开始计时，当且仅当题目 i 在它的期限截止以前被完成时，你才能获得 pi 的分数。完成期限的设定使得你不一定能将所有的题目全都按时完成。因此只有合理安排做题的顺序，才能在有限的时间内获得最高的分数。



　　问：在这种条件下，你能够得到的最高的分数是多少？



Input



第一行输入题目的总个数 n <= 10000

第二行输入各个题目的分数 0 < pi <= 100

第三行输入每一个题目的完成期限 0 < di <=10000



Output



输出最高的分数。-Descr iption



Now we are to complete the network classroom topics and struggle. Do you want to get a higher score , but finds himself a little low efficiency , so you write a program to calculate it:



Assuming a total of n topics, each topic i you need a unit of time to complete. While each topic i have a completion date and the corresponding fraction di pi. Here s completion date is after the start time should be di time units within ( including di) can not be accomplished late .



All questions simultaneously start the timer, if and only if its subject i is completed before the deadline , you can get pi score. Deadlines are set so you do not necessarily have all problems can all be completed on time . Reasonable arrangements to do so only the order of questions , for a limited period of time in order to get the highest score.



Q: In this condition, you can get the highest score is the number ?



Input



            The first line of input the total num