Hide

Problem J
Book Shelves

Languages en sv

You are going to buy book shelves to put all your books in. You already know how many books you have and need to count the number of book shelves required. The books have three sizes: a small book has width $1$, a medium book width $2$ and a big book width $3$. Each shelf has the same given width.

Given the number of books you have of each kind, write a program to compute the minimum number of shelves needed.

Input

The first line contains three integers that, in order, describe the number of small books, the number of medium books and the number of big books. There will be at most $20$ books of each kind.

The second line contains the integer $S$ ($S \le 20$), the width of a single shelf. You will always need at least $2$ shelves.

Output

Print the minimum number of shelves that you need to fit all the books.

Scoring

Your solution will be tested on a set of test case groups. To get the points for a group, you need to pass all the test cases in the group.

Group

Points

Constraints

$1$

$66$

There are at most $25$ books, and $S \le 10$.

$2$

$34$

No further constraints.

Sample Input 1 Sample Output 1
20 0 0
10
2
Sample Input 2 Sample Output 2
0 0 10
10
4
Sample Input 3 Sample Output 3
8 7 5
15
3
Sample Input 4 Sample Output 4
1 4 13
7
8