책장

면접 대비

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

요약

작은 책, 중간 책, 큰 책의 개수와 선반 크기가 주어질 때, 책을 나누지 않고 모든 책을 꽂는 데 필요한 선반의 최소 개수를 구합니다.

난이도: 보통10점 중 5점
유형: 동적 계획법
정답자: 아직 제출이 없습니다

문제

모든 책이 들어가도록 책장을 사려고 한다. 가지고 있는 책이 무엇인지는 미리 알고 있으며, 필요한 책장 수를 구해야 한다. 책은 세 가지 크기이다. 작은 책은 $1$ 공간 단위, 중간 크기 책은 $2$ 공간 단위, 큰 책은 $3$ 공간 단위를 차지한다. 책장 하나에는 정해진 수의 공간 단위가 들어간다.

크기별 책의 권수가 주어졌을 때, 모든 책을 넣는 데 필요한 책장 수를 가장 적게 만드는 값을 구하는 프로그램을 작성하라.

입력

첫 줄에는 작은 책, 중간 크기 책, 큰 책의 권수를 이 순서대로 나타내는 세 정수가 주어진다. 크기별 책의 권수는 각각 최대 $20$ 권이다.

다음 줄에는 책장 하나의 크기를 공간 단위로 나타내는 정수 $S$ ( $S \le 20$ )가 주어진다. 책장은 항상 최소 $2$ 개 필요하다.

출력

모든 책을 넣는 데 필요한 책장 수의 최솟값을 출력한다.

예제4

예제 1
입력
```
20 0 0
10
```
예상 출력
```
2
```
예제 2
입력
```
0 0 10
10
```
예상 출력
```
4
```
예제 3
입력
```
8 7 5
15
```
예상 출력
```
3
```
예제 4
입력
```
1 4 13
7
```
예상 출력
```
8
```