Problem H
Step Goals
Alice is an avid walker and always makes sure to reach her daily steps goal. She is always looking for new places to go on walks, and prefers nearby mountains which all have connected trails. Depending on how much activity she has already gotten on a particular day, Alice will have a different number of steps needed each day to meet her daily goal.
The mountains near Alice are no ordinary mountains. They appear to have no start and end, and are oddly shaped. Furthermore, these mountains all have connecting trails, which means that the end point of a trail is the start point of the next trail. Fortunately, Alice has a teleportation device that can take her to the start point of any trail and back from the trail’s end point! However, Alice can use the device she has only twice a day, once to teleport to a trail’s start point, and once to get back from the end point of the last connected trail she takes to the bottom of the mountain after she is done.
Alice wants to make sure she starts at a trail such that she can walk on the least number of trails possible while still meeting her step goals. Alice must keep walking in the same direction; she cannot turn around and repeat a trail to reach her step goal. Thus, she will continue walking until she meets her step goal, at which point she will teleport back to the bottom of the mountain.
Given the number of steps she wants to take that day and the connected trails with their distances, find the minimum number of consecutive trails she needs to walk to meet her steps goal.
Input
The first line of input will contain $2$ integers. The first integer $s$ ($1 \le s \le 10^9$) is the number of steps Alice will walk that day, and the second integer $n$ ($1 \le n \le 10^5$) is the number of trails that Alice can walk on. The second line will list $n$ integers $t$ ($0 \le t \le 1\, 000$) which provide the lengths of the connected trails (in order) in miles.
For Alice, $1 \text { step} = 1 \text { foot}$. There are $5\, 280$ feet in a mile.
Output
Display the minimum number of trails Alice will have to take to meet her steps goal for the day. If it is impossible for her to meet her step goals, then output IMPOSSIBLE.
| Sample Input 1 | Sample Output 1 |
|---|---|
22000 6 2 3 1 2 4 3 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
45000 3 3 1 1 |
IMPOSSIBLE |
