Problem G
Oil Change
Nancy has a number of gasoline-powered vehicles and she changes their engine oil regularly. They all use the same kind of engine oil, which she buys in $5$ litre containers. You can assume she has an unlimited supply of these $5$ litre containers full of oil, and that her vehicles have their full capacity of dirty oil before their oil change, and they have their full capacity of new oil after their oil change.
Here is her algorithm for changing the oil in single vehicle:
-
Place a pan under the vehicle.
-
Remove a plug that makes the oil drain out of the engine into the pan. (Once the plug is removed, she cannot put it back until all the oil in the engine has drained out.) If the pan overfills, there is an oil spill that damages the environment. Since Nancy is somewhat environmentally responsible (apart from owning a whole bunch of gasoline vehicles), she does not want this.
-
Replace the plug.
-
Add new oil from already-opened containers or from opening some $5$ litre containers (or both). This may end up creating some containers that are empty and some containers that are opened but only partly filled with new oil.
-
Optionally, add any desired amount of dirty oil from the pan to any (non-full) containers that do not contain any new oil. Make sure this does not overfill any container.
-
Write “take to recycling” on all containers that have dirty oil in them.
When Nancy starts changing the oil in a vehicle, she may have several containers partly full of clean oil, several containers partly full of dirty oil, and a pan that has some dirty oil in it.
Nancy has several vehicles needing oil changes, and has written down a list of them and how much oil each vehicle holds. For some reason, she insists on processing vehicles in the order on the list. When she starts the oil change on her first vehicle, the pan is empty and she has no empty or partly empty containers — only full containers of new oil.
Given the list of vehicles and the number of litres that pan will hold, can Nancy change the oil in all her vehicles without overfilling the pan and creating an environmental mess?
When she finishes all vehicles, it is okay for Nancy’s pan to have some dirty oil in it, and for her to have partly full containers of new oil, as well as partly full containers of dirty oil.
Input
The input starts with a single line containing two positive integers, $N$ and $P$, separated by a space. Both are at most $100$. Value $N$ represents the number of vehicles Nancy has. Value $P$ is a tiny bit less than the capacity of the pan. (The pan can hold $P$ litres of oil without overflowing.)
After this, we have $N$ rows, each with a positive integer no larger than $100$, representing the oil capacity of a vehicle.
Output
Output Overflow or No overflow, depending on whether Nancy can do her oil changes without creating an environmental mess, if she processes the vehicles in the given order.
Sample Input 1 | Sample Output 1 |
---|---|
2 10 4 7 |
Overflow |
Sample Input 2 | Sample Output 2 |
---|---|
3 9 4 4 6 |
No overflow |