In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
Byteasar studies computer science at the University of Bytetown. There is a snack vending machine at his faculty that sells types of snacks, numbered through . Snacks of different types may have different price, since they differ in size and flavor.
Recently Byteasar discovered that the vending machine is broken. If one buys a snack of type , the vending machine additionally dispenses one snack of each of the types , , ..., , provided that snacks of these types are available (if there are no snacks of some of the types , simply no snack of this type is dispensed). Buing snack of type is possible only if at least one snack of this type is available.
Byteasar decided to take advantage of the fault he discovered. He would like to find out what is the maximum total value (that is, the sum of prices) of snacks that he can obtain in the vending machine using a given amount of money. He does not have to use all the money.
The first line of input contains two integers and (, ): the number of types of snacks and the amount of money that Byteasar has at his disposal. The second line holds integers (), the prices of snacks of respective types. The third line holds integers (), the quantities of snacks of respective types that are available in the vending machine.
The only line of output should contain one integer: the total price of snacks that Byteasar can obtain in the vending machine using at most units of money.
For the input data:
6 8 7 2 3 5 7 2 1 3 0 3 2 1
the correct result is:
Explanation of the example: Byteasar buys a snack of type 6. The vending machine dispenses one snack of each of the types 1, 2, 4, 5 and 6. Next, Byteasar buys a snack of type 4. In addition to this snack, the vending machine dispenses one snack of type 2.
Task author: Jakub Pachocki.