Problem G
Group Lockers
Upon hearing this, a group of $n$ friends decides that they each want their own locker. None of them have any specific requirements about the size or location of their locker, except that — being such good friends — they want their lockers to be close to each other. In fact, they insist that all of their lockers belong to the same set of lockers. Within that set, they want to minimize the distance required to walk between the leftmost and rightmost lockers that belong to the friends.
Given a candidate set of lockers, and the number of lockers that are available for rent in each column, can you help the friends determine this distance if they choose their $n$ lockers optimally?
Input
The input consists of:
-
One line with two integers $n$ and $m$ ($1 \le n \le 10^9$, $1 \le m \le 5\cdot 10^5$), the number of friends and the number of columns in the candidate set of lockers.
-
One line with a string of $m$ digits $c_1c_2\ldots c_ m$ ($0 \le c_ i \le 4$), where $c_ i$ represents the number of available lockers in column $i$.
Output
Output the distance, measured in number of columns, required to walk between the leftmost and rightmost lockers that belong to the friends, assuming they rent the $n$ lockers that minimize this distance. If it is not possible to rent $n$ lockers, output “impossible”.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 10 0200110102 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 7 0401330 |
1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
4 3 224 |
0 |
| Sample Input 4 | Sample Output 4 |
|---|---|
10 10 0301010400 |
impossible |
