There is one orchard farm. On this farm, there are multiple trees to plant, each tree has a different time to grow and quantity. And after that time has passed, they generate the fruits. It is required to plant every tree at least once.

The trees after their growth period have ended, they produce a certain quantity every day.

After each tree has borne fruits, they are sold in the market for a set price to sell per kg.

You have to plant all the trees in the farm that will generate the maximum amount of money from this orchard farm.

Given that;

1. The first fruit tree is an apple tree, which produces 400 apples per tree & it takes 10 days for them to grow. There are 5 Apples in 1 kg, and the income is ₹ 150/kg.

2. The second fruit tree is an orange tree, which produces 280 oranges per tree & it takes 6 days for them to grow. There are 7 oranges in 1 kg, and the income is ₹ 250/kg.  

3. The third fruit tree is the mango tree, which produces 2200 mangoes per tree & it takes 15 days for them to grow. There are 8 mangoes in 1 kg, and the income is ₹ 100/kg.  

4. The fourth fruit tree is a lemon tree, which produces 1500 lemons per tree & it takes 5 days for them to grow. There are 10 lemons in 1 kg, and the income is ₹ 50/kg.  

5. The fifth fruit tree is a coconut tree, which produces 75 coconuts per tree & it takes 15  days for them to grow. There are 15 coconuts in 1 kg, and the income is ₹ 1600/kg. 

You have to plant trees which yield a maximum amount of money while making sure that you have planted at least one tree of each type and also have to make sure that, one type of tree can cover up to a maximum of 40% of the 100% of the plantation in the farm. Write an algorithm to provide an output of the amount you will make in given days.

T = Testcases

N = Number of trees

D = Number of Days

T

N D

Case #1: Total income

1<T<100 (small)

1<T<1000 (large)

10<N<60 (small)

10<N<75 (large)

15<D<1000 

1. Small Input

2. Large Input