The CS department has just had a big party and ordered too
much pizza. Now it is time to put away the leftovers. They
ordered a number of small, medium, and large pizzas, and there
are still slices remaining in some or all of the pizza boxes. A
small pizza comes in 6 slices, a medium pizza in 8 slices, and
a large pizza in 12 slices. To save space, you can combine the
leftover slices from the same size pizzas into a box of the
right size, but you can’t put a slice into a box for a
different sized pizza, and you can’t put more slices into a box
than it originally held. What is the smallest number of boxes
you will need to hold all the leftovers?
Input
The first line of input contains one positive integer
$n$ ($n < 1000$), the number of pizzas
that were ordered. Each of the following $n$ lines contains two items
$s_i$ and $l_i$ (separated by a space)
representing the leftovers for a given pizza. $s_i$ is a string S, M, or L representing the size of pizza $i$, and $l_i$ is an integer representing the
number of leftover slices for pizza $i$. You can assume that each
$l_i$ is between zero and
the original number of slices of that size pizza,
inclusive.
Output
Output a single number, the fewest possible total boxes that
can hold the leftover pizza according to the constraints given
above.
| Sample Input 1 |
Sample Output 1 |
3
S 0
M 5
L 0
|
1
|
| Sample Input 2 |
Sample Output 2 |
3
S 3
S 4
S 2
|
2
|
| Sample Input 3 |
Sample Output 3 |
4
S 1
M 1
M 3
L 1
|
3
|
| Sample Input 4 |
Sample Output 4 |
4
L 6
M 2
M 6
L 6
|
2
|
