课程结束后,n 组学生走到外面,决定去拜访波利卡波斯庆祝他的生日。我们知道第 i 组由 si 个朋友组成(1 ≤ si ≤ 4),他们想一起去波利卡普斯。他们决定乘出租车前往那里。每辆车最多可搭载四名乘客。如果每个团体的所有成员都乘坐同一辆出租车(但一辆出租车可以搭载多个团体),那么孩子们至少需要多少辆汽车?
输入
第一行包含整数 n (1 ≤ n ≤ 105) — 学童组数。第二行包含整数序列 s1, s2, ..., sn (1 ≤ si ≤ 4)。整数之间用空格分隔,si 是第 i 组中孩子的数量。
输出
打印出单个数字 — 载所有儿童前往波利卡普斯所需的出租车最少数量。
示例
输入 #1
5 1 2 4 3 3
输出 #1
4
输入 #2
8 2 3 4 4 2 1 3 1
输出 #2
5
注意
在第一个测试中,我们可以将孩子们分类到四辆车中,如下所示:
- 第三组(由四个孩子组成),
- 第四组(由三个孩子组成),
- 第五组(由三个孩子组成),
- 第一组和第二组(分别由一个和两个孩子组成)。
还有其他方法可以将组分为四辆车。