Pieguy и Piegirl играют в игру. У них есть корневое бинарное дерево, которое обладает следующим свойством: каждая вершина дерева либо лист, либо имеет ровно два сына. Каждый лист имеет некоторое значение, ассоциированное с ним.
Во время игры игроки по очереди делают ходы. На своем ходу игрок выбирает два листа, имеющих общего непосредственного предка, и удаляет их. При этом он ассоциирует с общим предком листов (после удаления он станет листом) какое-то одно из ассоциированных с ними значений на свой выбор. Игра заканчивается, когда в дереве остается ровно одна вершина — корень дерева.
Pieguy ходит первым и его цель — максимизировать значение, которое будет ассоциировано с корнем в конце игры. Piegirl, наоборот, хочет минимизировать это значение. Считая, что оба игрока играют оптимально, вычислите значение, которое будет ассоциировано с корнем в конце игры.