Taxi

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

Each of n groups contains 1..4 students. A taxi carries at most four and no group may be split. Groups may share a taxi. Minimize the number of taxis.

Input

First n, then n group sizes.

Output

The minimum number of taxis.

Subtasks

• Subtask 1 (20%): n ≤ 20.

• Subtask 2 (30%): n ≤ 1000.

• Subtask 3 (50%): n ≤ 100000.

Examples

Example 1

Input:

5
1 2 4 3 3

Output:

4

Explanation: Group 4 uses one taxi; each group 3 another; groups 1 and 2 share one.

Example 2

Input:

4
1 1 1 1

Output:

1

Explanation: All four single-person groups share a taxi.