Рекурсивный перебор

Дан лабиринт в виде прямоугольной таблицы N×M. Символ '.' — проход, символ '#' — стена. Найдите количество различных путей из левого верхнего угла (0,0)  в правый нижний угол (N-1, M-1).
Двигаться можно только вправо или вниз. Проходить через одну клетку дважды нельзя.

Формат входных данных
Первая строка: два числа N и M — размеры лабиринта (2 ≤ N, M ≤ 5)
Следующие N строк: лабиринт (символы '.' и '#')

Формат выходных данных
Одно число — количество различных путей.
Если путей нет, вывести 0.
 

Примечание

В тестовом примере существуют два пути
Путь 1: (0,0)→(1,0)→(2,0)→(2,1)→(2,2)
Путь 2: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)

ПОДСКАЗКА:
1. Отмечай посещённые клетки, чтобы не ходить по кругу
2. При откате снимай отметку о посещении
3. Проверяй границы лабиринта и стены
 

Много студентов живут в общежитии. Общежитие — это большой мир веселых развлечений и возможностей, но у него есть свои минусы.
В общежитии всего один душ, а желающих принять душ утром, конечно, больше. Поэтому каждое утро перед душем общежития образуется очередь из пяти человек.
Как только душ открывается, первый человек из очереди заходит в душ. Спустя некоторое время, когда первый зашедший выходит из душа, следующий заходит в душ. Этот процесс продолжается, пока все в очереди не примут душ.

Душ — дело не быстрое, поэтому во время ожидания студенты общаются. В каждый момент времени студенты общаются парами: (2*i - 1)-й человек в очереди (на текущий момент) общается с (2*i)-м.
Рассмотрим этот процесс подробнее. Обозначим людей цифрами от 1 до 5. Пусть изначально очередь имеет вид 23154 (человек 2 стоит в начале очереди). Тогда перед открытием душа 2 общается с 3, 1 общается с 5, 4 ни с кем не общается. Затем 2 заходит в душ. Пока 2 принимает душ, 3 и 1 общаются, а также 5 и 4 общаются. Затем 3 заходит в душ. Пока 3 принимает душ, 1 и 5 общаются, 4 ни с кем не общается. Затем 1 заходит в душ, а пока он принимает душ, 5 и 4 общаются. Затем 5 заходит в душ, а затем 4 заходит в душ.

Известно, что если студенты i и j общаются, то радость студента i увеличивается на gi,j, а радость студента j увеличивается на gj,i.  Вам надо найти такой изначальный порядок студентов в очереди, чтобы суммарная радость всех студентов в итоге была максимальной. Стоит заметить, что некоторые студенты могут общаться несколько раз. В приведенном выше примере студенты 1 и 5 общаются пока ждут открытия душа, а также пока 3 принимает душ.

Сегодня возле душа выстроилась очередь ровно из 5 студентов. Найдите максимально возможную суммарную радость этих студентов.

Входные данные
Входные данные состоят из пяти строк, в каждой строке записано пять целых чисел разделенных пробелом: j-е число в i-й строке обозначает gi,j (0 ≤ gi,j≤ 10⁵). Гарантируется, что gi,i = 0 для всех i.
Считайте, что студенты пронумерованы от 1 до 5.

Выходные данные
Выведите единственное целое число — максимально возможную суммарную радость студентов.
 

В каком-то другом мире сегодня 31 декабря. Дед Кокованя решил приготовить многомерный бургер, который так любит Дарёна. Бургер уровня L (L - целое число, большее или равное 0) готовится следующим образом:

• Бургер нулевого уровня - это котлета.
• Бургер с уровнем L (L >= 1) - это булочка, бургер с уровнем (L-1), котлета, бургер с другим уровнем (L-1) и еще одна булочка, уложенные вертикально в указанном порядке, считая снизу.

Например, бургер уровня 1 и бургер уровня 2 выглядят как БКККБ и ББКККБКБКККББ (повернутые на 90 градусов), где Б и К обозначают булочку и котлету.

Бургер, который приготовит дед Кокованя, - это бургер уровня N. Дарёна всегда съедает только Х слоев нижней части бургера (слой - это котлета или булочка). Сколько котлет она съест?


Входные данные
Программа получает на вход 2 целых числа через пробел: N и X (1 <= N <= 50, 1 <= X <= (общее количество слоев в бургере N-го уровня)).

Выходные данные
Выведите количество котлет в самых нижних X слоях, считая от нижней части бургера уровня N.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 7	4	В самых нижних 7 слоях бургера второго уровня ( ББКККБКБКККББ) находятся 4 котлеты.
2	1 1	0
3	50 4321098765432109	2160549382716056	Бургер 50-го уровня довольно толстый настолько, что количество его слоев не укладывается в 32-битное целое число.

В Волшебной стране используются монетки достоинством A₁, A₂,..., A_M. Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.

Входные данные
На вход программы  сначала поступает число N (1 <= N <= 10⁹), затем - число M (1 <= M <= 15) и далее M попарно различных чисел A₁, A₂,..., A_M (1 <= A_i <= 10⁹).

Выходные данные
Сначала выведите K - количество монет, которое придется отдать Волшебному человечку, если он сможет заплатить указанную сумму без сдачи. Далее выведите K чисел, задающих достоинства монет. Если решений несколько, выведите вариант, в котором Волшебный человек отдаст наименьшее возможное количество монет. Если таких вариантов несколько, выведите любой из них.

Если без сдачи не обойтись, то выведите одно число 0. Если же у Волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число -1 (минус один).
 

Ввод	Вывод
100 6 11 20 30 40 11 99	3 40 30 30