Bookshelves

Interview

Time limit1sMemory limit1024 MB

Summary

Given counts of small, medium, and large books and the shelf size, find the fewest shelves needed to hold all books without splitting any book.

Level: Medium5 of 10
Topics: Dynamic programming
Solved: No attempts yet

Problem

You are buying bookshelves to fit all of your books. You already know which books you have and need to work out how many shelves are required. The books come in three sizes: a small book takes $1$ space unit, a medium book takes $2$ , and a large book takes $3$ . Each shelf holds a fixed number of space units.

Given how many books of each size you have, write a program that computes the fewest shelves needed to fit all of them.

Input

The first line contains three integers: the number of small books, the number of medium books, and the number of large books, in that order. The number of books of each size is at most $20$ .

The next line contains an integer $S$ ( $S \le 20$ ), the size of one shelf in space units. At least $2$ shelves are always required.

Output

Print the minimum number of shelves needed to fit all the books.

Examples4

Example 1
Input
```
20 0 0
10
```
Expected output
```
2
```
Example 2
Input
```
0 0 10
10
```
Expected output
```
4
```
Example 3
Input
```
8 7 5
15
```
Expected output
```
3
```
Example 4
Input
```
1 4 13
7
```
Expected output
```
8
```