URI Online Judge | 1966

The Voyage Home

By Leandro Zatesko, UFFS BR Brazil

Timelimit: 1

This problem is dedicated to all of us who study or work far from the city where our families live!

John loves cheese. Mozzarella, Parmesan, Provolone, it doesn't matter, he loves them all. John likes cheese so much that he puts cheese in everything he cooks, even in desserts. John's family is as crazy about cheese as him. As this weekend he is going to visit his relatives, who live far away, he decided to take for them a bit of Chapecoense cheese. John intends to organise a party as soon as he arrives in his hometown. The idea is to chop all the cheese he takes in cubes of side 1 cm and to assemble a pyramid with them as the pyramid of the figure, which has 5 cheese cubes in its base. Maybe it won't be possible for him using all the cheese cubes in the construction of the pyramid. In this case, John eats all the cheese that is left.

In Chapecó's cheese store, there is cheese in many sizes and prices, all of parallelepiped shape. It is not necessary to buy a whole piece of cheese. One can ask for a specific volume, for example:

— Mr. Chee, could you please cut for me a piece of 20 cm × 10 cm × 30 cm of Parmesan cheese?

John was with a restrict budget for buying the cheese to take for his family, but even so he bought the greatest cheese volume he could respecting the budget he designated for that.


The first input line consists of two integers, N and B (1 ≤ N ≤ 105, 0 ≤ B ≤ 109), which represent respectively the number of pieces of cheese in the store and John's budget. The second input line consists of N integers vi (1 ≤ vi ≤ 104, 1 ≤ iN), each one representing the volume, in cubic centimetres, of the ith piece of cheese. The last input line consists of N integers pi (0 ≤ pi ≤ 104, 1 ≤ iN), each one representing the price of the ith piece of cheese.


Print a line containing singly the number of cheese cubes that the base of John's pyramid will have.

Input Sample Output Sample

3 5
2 1 5
3 1 2