Taxi

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có n nhóm học sinh; nhóm thứ i có s_i em (1..4). Một xe taxi chứa tối đa 4 người và không được tách bất kỳ nhóm nào ra nhiều xe; có thể ghép nhiều nhóm trên một xe nếu đủ chỗ. Tìm số taxi ít nhất để đưa tất cả nhóm đi.

Input

Dòng đầu n; dòng tiếp theo n số s_i.

Output

Một số nguyên là số taxi tối thiểu.

Subtask

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

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

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

Ví dụ

Ví dụ 1

Input:

5
1 2 4 3 3

Output:

4

Giải thích: Nhóm 4 một xe; hai nhóm 3 mỗi nhóm một xe; nhóm 1 và 2 ghép một xe.

Ví dụ 2

Input:

4
1 1 1 1

Output:

1

Giải thích: Bốn nhóm một người ghép chung một xe.