Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

TriCoder Tournament

Limits: 1s, 512 MB

This year, KUET is hosting the TriCoder tournament. Two other universities have joined this tournament and brought their best programmers . One programmer will be selected as champion from each of the universities and three of them have to compete against each other in three tasks. Each task consists of a number of programming problems. Judges will decide the winner based on result. Now Rifat somehow becomes the fourth champion of the competition. (And oddly enough judges let him compete).

Rifat is a very good programmer. So he managed to pass first two task easily. Now he has to face the third task. This time if he fails to solve any of the problems the computer will chase him with a big machete. (চাপাতি) (I dont know how that’s possible). Rifat is sure he can solve all the problems . But he is also a cautious man. So he wants some kind of magical protection. After all he doesn’t like machete.

He went to the departmental store of KUET. The store has N magical items. Their prices are denoted by array A. ( ith item cost Ai taka). There is also a weird rule here. If Rifat buys ith item, then he cannot buy more than Bi items. For example array B = {5, 2, 3, 5}. He can buy 2nd and 3rd item, 1st, 3rd and 4th item etc. But he can’t buy 2nd , 3rd and 4th item. Because if he buys 2nd item then he can buy only two of them. His budget is X taka. Tell him maximum number of items he can buy.

Input

Input starts with two integers N and X (1 <= N <= 106, 1 <= X <= 109) , where N is number of items and X is Rifat’s budget. Next line contains n integers. ith of them denotes Ai (1 <= Ai <= 109) , the price of ith item. Next line contains N more integers. ith of them denotes Bi (1 <= Bi <= 109).

Output

Print one integer denoting maximum number of items Rifat can buy.

Samples

InputOutput
5 6                                                                             
1 2 1 4 6
3 3 3 3 1
3
InputOutput
6 10
3 4 4 5 5 6
1 2 3 4 5 5
2

For the first input Rifat can buy 1st, 2nd and 3rd item.

For second sample case You can select 2nd and 3rd item.

Discussion