The instructor's kids love playing with LEGO. Just give them a box of these magical bricks and everything is awesome1.

Lately, they have been working on organizing their gigantic collection of bricks 2. As they were sorting their 1x1, 2x1, 3x1 and 4x1 bricks, however, they got side-tracked with the following problem:

Given a collection of 1x1, 2x1, and 3x1, and 4x1 bricks, at least how many 4x1 rows are required to hold all the pieces?

Note, the kids are very particular and only want the bricks in a horizontal orientation.

For example, given 3 1x1 bricks, 2 2x1 bricks, 2 3x1 bricks, and 3 4x1 bricks, we would need 7 4x1 rows as shown on the right.

Because they have a lot of bricks, the kids want "daddy's students" to help them by writing a program that will compute the minimum number of rows needed to arrange their Nx1 bricks in 4x1 rows.

Input

Each line of input will consist of four numbers corresponding to the number of 1x1, 2x1, 3x1, and 4x1 bricks.

You should read and process each line of input until the end of the file.

Example Input

3 2 2 3

Output

For each collection of bricks, you should output the minimum number of 4x1 rows required to hold all the bricks as described above.

Example Output

7

Programming Challenges

This is based on the 311 - Packets problem on the UVa Online Judge.

Algorithmic Complexity

For each input test case, your solution should have the following targets:

Time Complexity O(1)
Space Complexity O(1)

Your solution may be below the targets, but it should not exceed them.

Submission

To submit your work, follow the same procedure you used for [Reading 01]:

$ cd path/to/cse-30872-fa21-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitHub

$ git checkout -b challenge10               # Create and checkout challenge10 branch

$ $EDITOR challenge10/program.cpp           # Edit your code

$ git add challenge10/program.cpp           # Stage your changes
$ git commit -m "challenge10: done"         # Commit your changes

$ git push -u origin challenge10            # Send changes to GitHub

To check your code, you can use the .scripts/check.py script or curl:

$ .scripts/check.py
Checking challenge10 program.cpp ...
  Result Success
    Time 0.02
   Score 6.00 / 6.00

$ curl -F source=@challenge10/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa21/challenge10
{"result": "Success", "score": 6, "time": 0.016405344009399414, "value": 6, "status": 0}

Pull Request

Once you have committed your work and pushed it to GitHub, remember to create a pull request and assign it to the appropriate teaching assistant from the Reading 05 TA List.


  1. You're welcome. 

  2. By they, I really mean my wife.