Problem B
Indoorienteering

Lukáš really likes orienteering, a sport that requires locating control points in rough terrain. To entertain the NWERC participants Lukáš wants to organize an orienteering race. However, it would be too harsh for the participants to be outdoors in this cold Swedish November weather, so he decided to jump on the new trend of indoor races, and set the race inside the B building of Linköping University.
Lukáš has already decided on the locations of the control points. He has also decided on the exact length of the race, so the only thing remaining is to decide in which order the control points should be visited such that the length of the total race is as he wishes. Because this is not always possible, he asks you to write a program to help him.
Note from the organizer: the NWERC indoorienteering race for this year has been cancelled since we neglected to apply for an orienteering permit in time from the university administration. (We still need you to solve the problem so that we can organize it for next year.)
Input
The input consists of:
-
one line with two integers
( ) and ( ), the number of control points and the desired length of the race, respectively; -
lines with integers each. The th integer on the th line, , denotes the distance between control point and ( for , and ). For all it is the case that and .
Output
Output one line with “possible” if
it is possible to visit all control points once in some order
and directly return to the first one such that the total
distance is exactly
Sample Input 1 | Sample Output 1 |
---|---|
4 10 0 3 2 1 3 0 1 3 2 1 0 2 1 3 2 0 |
possible |
Sample Input 2 | Sample Output 2 |
---|---|
3 5 0 1 2 1 0 3 2 3 0 |
impossible |