Problem H
Healthy Headgear
You have decided to start your own face mask factory to produce face masks with custom prints. The orders are in already even though you haven’t set up the factory for production yet. The machines needed for the production are expensive and you want to buy as few as possible while still being able to fulfill all orders within the agreed delivery deadline. Modern manufacturing technology has come a long way and the production machines can operate fully automatic all day long without any human interaction or maintenance.
All orders ask for a certain number of face masks with the same unique print. The machines have a start-up time for adjusting to a new print and make $10$ at the same time. So the time it takes to produce $1$ face mask is the same as $10$ (a machine can’t produce different prints at the same time). One can formulate the time in seconds it takes to produce one order of $n$ face masks as:
\begin{equation} t(n) = 20 + 10* \Bigg\lceil \frac{n}{10} \Bigg\rceil \end{equation}To be fair to your customers, you want to start production of the orders in the same order as you got them. Luckily, all customers have agreed to the same delivery deadline in their contract.
You have also decided that the orders won’t be split up and ran on multiple machines, as you would have to repackage the output from the machines. Right now, there is no machine that can do such a job, and it’s just too time consuming to do it with humans.
What is the smallest number of machines that would make it possible to finish all orders in time?
Input
The first line consists of two integers $T$ and $N$, the total time you have to produce all the face masks, and the number of orders of face masks respectively. Next follows one line with $N$ integers $n_ i$, each denoting the size of a batch.
Output
Output the smallest number of machines you have to invest in in order to complete all batches within the total time $T$. If it is not possible to complete all orders within the deadline output “impossible”.
Limits
-
$0 < T \leq 1\, 000\, 000$
-
$0 \leq N \leq 1\, 000\, 000$
-
$0 < n_ i \leq 10\, 000$
| Sample Input 1 | Sample Output 1 |
|---|---|
100 3 1 1 1 |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
60 3 3 13 11 |
3 |
