Minimum Amount Problem

★★★★★

6 votes

Implementation, Basic Programming, Dynamic Programming, Medium, Basics of Implementation

Details

Problem

There are $three$ types of fruits $T_1, T_2,$ and $T_3$ in a shop. Each fruit of type $T_1, T_2,$ and $T_3$ gives energy $2, 3,$ and 5 respectively.
The number of fruits of type $T_1, T_2,$ and $T_3$ are $Cnt_1, Cnt_2,$ and $Cnt_3$ respectively and each fruit cost $Cost_1, Cost_2,$ and $Cost_3$ respectively.
You want to get a total of S energy by buying some of the fruits, but you want to spend as less as possible.
So, find the minimum amount you need to spend.
Print "-1" if the answer does not exist.
Input format
- First line : S represents total amount of energy.
- Second line : Three space-separated integers $Cnt_1$ , $Cnt_2$ , and $Cnt_3$
- Third line : Three space-separated integers $Cost_1$ , $Cost_2$ , and $Cost_3$

Output format
Print the answer.

Constraints
$1 \le S \le 3 \times 10^4$
$1 \le Cnt_i \le 7 \times 10^3$ for $1 \le i \le 3$
$1 \le Cost_i \le 7 \times 10^3$ for $1 \le i \le 3$

Sample Input

10
2 2 1
5 5 20

Sample Output

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

We can make a total of energy $10$ by two ways :-
Case 1 :- Buying two $T_1$ , two $T_2$ . So this will cost $20$ .
Case 2 :- Buying one $T_1$ , one $T_2$ , one $T_3$ , So this will cost $30$ .

So, the minimum is $20$ .

Contributers:

Shubham Badkur

Rivu Das