Орієнтування#7859
Лукашу дуже подобається спортивне орієнтування — спорт, що вимагає знаходження контрольних точок на пересіченій місцевості. Щоб розважити учасників NWERC, Лукаш вирішив організувати змагання з орієнтування. Однак, через холодну шведську листопадову погоду, він вирішив провести змагання в приміщенні — в будівлі B Університету Лінчепінга.
Лукаш вже визначив місцезнаходження контрольних точок. Він також визначив точну тривалість гонки, тому залишилося лише вирішити, в якому порядку слід відвідувати контрольні точки, щоб загальна тривалість гонки відповідала його бажанню. Оскільки це не завжди можливо, він просить вас написати програму, яка допоможе йому.
Складаються з:
рядка з двох чисел (2 \le n \le 14) і (1 \le L \le 10^{15}) — кількість контрольних точок і бажана довжина гонки;
рядків по цілих чисел. -те число в -му рядку d_{ij} вказує на відстань між контрольними точками і (1 \le d_{ij} \le L для i \ne j і d_{ii} = 0). Для всіх 1 \le i, j, k \le n виконується d_{ij} = d_{ji} і d_{ij} \le d_{ik} + d_{kj}.
Виведіть possible, якщо існує можливість відвідати всі контрольні точки один раз у певному порядку, повернувшись до першої, так щоб загальна пройдена відстань дорівнювала точно . Інакше виведіть impossible.
Приклад 1
Приклад 2