Rods

Interview

Time limit1sMemory limit1024 MB

Summary

Given three rod lengths with limited counts of each, find the fewest rods whose total length reaches at least L, or print 0 if impossible.

Level: Medium5 of 10
Topics: Greedy, Brute force, Math, Implementation
Solved: No attempts yet

Problem

We have rods of 3 lengths $a_1$ , $a_2$ , and $a_3$ centimeters, with $b_1$ , $b_2$ , and $b_3$ rods of each length respectively. We must line up some of these rods tightly end to end along their length so that the total length obtained is equal to or greater than $L$ centimeters.

Write a program rods that computes the smallest number of rods we can use.

Input

The first line of the standard input contains the given integers in the following order: $a_1$ , $a_2$ , $a_3$ , $b_1$ , $b_2$ , $b_3$ , $L$ . The numbers in the input are separated by spaces.

Output

On the first line of the standard output, the program must print one integer equal to the requested count. If it is impossible to line up the rods according to the requirement, your program must print the number 0.

Constraints

All numbers in the input are integers, positive, and less than 100.

Examples3

Example 1
Input
```
1 1 1 1 1 1 5
```
Expected output
```
0
```
Example 2
Input
```
3 2 1 10 11 12 18
```
Expected output
```
6
```
Example 3
Input
```
4 1 3 4 5 8 19
```
Expected output
```
5
```