Module: Greedy Algorithms


Problem

1 /9


Formaggio buys panzerotti

Theory Click to read/hide

A greedy algorithm is an algorithm that at each step chooses the optimal (within the current step) variant in the expectation that the final solution will be optimal in the global sense.

Small example:
Suppose we have an unlimited number of coins of different denominations and we need to collect the amount S. Let's consider two specific cases, each of which we will try to solve with a greedy algorithm.
Namely, we will act as follows: at each step we will take a coin of the highest denomination (the best option within the step), which does not exceed the remaining amount.

a) Let the coin denominations be 1, 5 and 10, and S = 27.
1) Take 10, S: 27 -> 17
2) Take 10, S: 17 -> 7
3) Take 5, S: 7 -> 2
4) Take 1, S: 2 -> 1
5) Take 1, S: 1 -> 0
As a result, they scored the amount of five coins. You can independently (for example, brute force) make sure that for 4 coins or less you will not be able to score 27.

b) Let the denominations of the coins be 1, 5 and 7, and S = 24.
1) Take 7, S: 24 -> 17
2) Take 7, S: 17 -> 10
3) Take 7, S: 10 -> 3
4) Take 1, S: 3 -> 2
5) Take 1, S: 2 -> 1
6) Take 1, S: 1 -> 0.
We scored with six coins, but could score S with four coins - two with a face value of 7 and two with a face value of 5.

As can be seen from the example, it is not always possible to solve problems with a greedy algorithm. But if it leads to an overall optimal answer, then it will usually be easier than using dynamic programming or other methods.

Problem

Formaggio is very fond of panzerotti with various fillings, and it is not so important with which one. Once, being in a hungry state, Formaggio went into a bakery and saw that panzerotti with tomatoes, spinach and mushrooms were on sale.
Formaggio wants to buy as many panzerotti as possible, but the problem is that the number of panzerotti on sale is limited, just like Formaggio's money.

Help Formaggio determine the maximum number of panzerotti he can buy.

Input:
The first line contains the numbers P1, P2 and P3 – the cost of panzerotti with tomatoes, spinach and mushrooms respectively.
The second line defines the values ​​N1, N2 and N3 – number of matching panzerotti on sale. 
The third line contains the number R – the amount of money Formaggio has. 
All numbers in the input are positive integers not exceeding 10000.

Output:
Print a single integer - the maximum number of panzerotti that Formaggio can buy.

Example:
 
Input Output
5 3 8
2 6 4
23
7