e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Задачі

Логічне дерево

Логічне дерево

Розглянемо різновидь двійкового дерева, який ми назвемо логічним деревом. У цьому дереві кожен рівень повністю заповнено, за винятком, можливо, останнього (самого глибокого) рівня. При цьому, усі вершини останнього рівня знаходяться максимально ліворуч. Додатково, кожна вершина дерева має ноль або двох дітей.

Кожна вершина дерева має пов'язане з нею логічне значенея (1 або 0). Крім цього, кожна внутрішня вершина має пов'язану з нею логічну операцію ("І" чи "АБО"). Значення вершини з операцією "І" - це логічне "І" значень її дітей. Аналогічно, значення вершини з операцією "АБО" - це логічне"АБО" значень її дітей. Значення усіх листків задаються у вхідному файлі, тому значення усіх вершин дерева можуть бути знайдені.

Найбільшу цікавість для нас становить корінь дерева. Мы хочемо, щоб він мав задане логічне значення v, яке може відрізнятись від поточного. На щастя, ми можемо змінювати логічні операції деяких внутрішніх вершин (замінити "І" на "АБО" та навпаки).

Задано опис логічного дерева та набір вершин, операції в яких можуть бути змінені. Знайдіть найменшу кількість вершин, які слід змінити, щоб корінь дерева прийняв задане значення v. Якщо це неможливо, то виведіть рядок "IMPOSSIBLE" (без лапок).

Вхідні дані

У першому рядку вхідного файлу знаходяться два числа n та v (1n10000, 0v1) - кількість вершин у дереві та потрібне значення у корені відповідно. Оскільки усі вершини мають ноль або двох дітей, то n - непарне. Наступні n рядків описують вершини дерева. Вершини нумеруються від 1 до n. Перші (n-1)/2 рядків описують внутрішні вершини. Кожен з них містить два числа - g та c, які приймають значення або 0, або 1. Якщо g=1, то вершина задає логічну операцію "І", інакше вона задає логічну операцію "АБО". Якщо c=1, то операція у вершині може бути змінена, інакше ні. Внутрішня вершина з номером i має дітей 2i та 2i+1. Наступні (n+1)/2 рядків описують листки. Кожен рядок містить одне число 0 або 1 - значення листка.

Вихідні дані

У вихідний файл виведіть відповідь до задачі.

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
17 1
0 1
1 0
1 0
1 1
0 1
1 1
1 1
1 1
0
1
0
1
0
0
1
0
1
Вихідні дані #1
2