Ms. Rita is a Jewellery Shop owner in Pew Market. Some out of towners came to visit a place nearby. Ms. Rita doesn’t want to miss the chance of selling her best products to the visitors.
So, she takes out the largest box she has and starts loading her products. As she has to sell the products, she can not break the products into pieces to fit them. So, she wants to fit the most valuable jewellery products in the box.
She has products and a box of size and she knows all the products’ sizes and values.
You are given all the information and have to tell the maximum total value of the products she can fit in the box and the total values left in the shop.
The first line will contain two space integers and , the number of products and the maximum capacity of the box.
The second line contains space-separated integers, denoting the sizes of products.
The third line contains separated integers, denoting the values of products.
All the integers in the test cases will be less than or equal to .
You have to output two integers, the maximum total value of the products she can fit in the box and the total values left in the shop.
Input | Output |
---|---|
4 9 4 2 3 6 3 7 6 4 | 16 4 |
Input | Output |
---|---|
4 13 3 4 6 1 2 1 4 3 | 9 1 |
Ms. Rita can fit the product with values 2, 4 and 3 making the total weight 10 which is less than 13, the box capacity. And it can be shown that this is the best answer. So, Ms. Rita can take items total worth 9 taka and the total products values left in the shop is 1 taka. |