막대기

면접 대비

시간 제한1초메모리 제한1024 MB

요약

세 가지 길이의 막대가 각각 정해진 개수만큼 있을 때, 총 길이가 L 이상이 되도록 사용하는 막대 수의 최솟값을 구하고 불가능하면 0을 출력한다.

난이도: 보통10점 중 5점
유형: 그리디, 완전 탐색, 수학, 구현
정답자: 아직 제출이 없습니다

문제

길이가 $a_1$ , $a_2$ , $a_3$ 센티미터인 막대기가 있고, 각 길이의 막대기 개수는 각각 $b_1$ , $b_2$ , $b_3$ 개다. 이 막대기 중 몇 개를 골라 길이 방향으로 빈틈없이 이어 붙여서 전체 길이가 $L$ 센티미터 이상이 되도록 해야 한다.

사용할 수 있는 막대기 개수의 최솟값을 구하는 프로그램 rods를 작성하시오.

입력

표준 입력의 첫째 줄에 정수 $a_1$ , $a_2$ , $a_3$ , $b_1$ , $b_2$ , $b_3$ , $L$ 이 이 순서대로 주어진다. 입력의 수들은 공백으로 구분된다.

출력

표준 출력의 첫째 줄에 구하는 개수를 하나의 정수로 출력한다. 조건에 맞게 막대기를 이어 붙이는 것이 불가능하면 0을 출력한다.

제한

입력의 모든 수는 양의 정수이고 100보다 작다.

예제3

예제 1
입력
```
1 1 1 1 1 1 5
```
예상 출력
```
0
```
예제 2
입력
```
3 2 1 10 11 12 18
```
예상 출력
```
6
```
예제 3
입력
```
4 1 3 4 5 8 19
```
예상 출력
```
5
```