Mutalisk

Interview

Time limit2sMemory limit512 MB

Summary

Given the health of at most 3 SCVs, find the fewest attacks that deal 9, 3, 1 damage in some order to distinct SCVs and destroy them all.

Level: Medium6 of 10
Topics: Dynamic programming, Brute force
Solved: No attempts yet

Problem

Subin is playing StarCraft against Gangho. Subin has one Mutalisk left and Gangho has $N$ SCVs left. The SCVs cannot attack the Mutalisk, so the game is already decided. What remains is the number of attacks needed to destroy every SCV.

One attack of the Mutalisk can hit up to three different SCVs.

The SCV hit first loses 9 health.
The SCV hit second loses 3 health.
The SCV hit third loses 1 health.

The same SCV cannot be hit more than once within a single attack. An SCV is destroyed the moment its health drops to 0 or below.

Given the remaining health of the SCVs, write a program that finds the minimum number of attacks needed to destroy all of them.

Input

The first line contains the number of SCVs $N$ ( $1 \le N \le 3$ ). The second line contains the health of the $N$ SCVs, separated by spaces. Each health value is a natural number no greater than 60.

Output

Print the minimum number of attacks needed to destroy every SCV on the first line.

Hint

Consider three SCVs with health 12, 10 and 4. Hitting them in the order 1, 3, 2 leaves $(12-9, 10-1, 4-3) = (3, 9, 1)$ . Hitting them next in the order 2, 1, 3 leaves $(3-3, 9-9, 1-1) = (0, 0, 0)$ , so two attacks are enough.

Examples5

Example 1
Input
```
3
12 10 4
```
Expected output
```
2
```
Example 2
Input
```
3
54 18 6
```
Expected output
```
6
```
Example 3
Input
```
1
60
```
Expected output
```
7
```
Example 4
Input
```
3
1 1 1
```
Expected output
```
1
```
Example 5
Input
```
2
60 40
```
Expected output
```
9
```