Последовательность из трех комнат соединена между собой автоматическими дверьми.

Каждая дверь управляется карточкой безопасности. Как только в комнату заходят, дверь автоматически закрывается и эта карточка безопасности повторному использованию не подлежит. Автомат в начальной точке выдает неограниченное число карточек, однако в каждой из комнат (в том числе и в начальной) установлены сканнеры, и если они обнаружат у владельца более трех карточек, или же обнаружат карточку на полу, то все двери необратимо запираются. В то же время, во всех комнатах есть ящик для хранения любого числа карточек безопасности для использования на более поздних этапах.

Если попытаетесь просто пройти через все комнаты по очереди, то, когда окажетесь в комнате 3, все карточки будут израсходованы, и вы навсегда останетесь в этой комнате!

Но если воспользоваться ящиками для хранения, то побег возможен. К примеру, можно зайти в 1 комнату при помощи первой карточки, полощить в ящик хранения вторую карточку, а третьей карточкой вернуться обратно в начальную комнату. Пополнив в автомате запасы тремя дополнительными карточками, можно войти в первую комнату и забрать карточку из ящика хранения. Теперь у вас снова три карточки, и вам удастся пройти через оставшиеся три двери. Этот способ позволяет пройти через все три комнаты, воспользовавшись в общей сложности 6 карточками.

Через шесть комнат возможно пройти, истратив 123 карточки безопасности, имея на руках в любой из комнат не более 3 карточек.

Пусть C - максимальное допустимое системой число карточек на руках.

Пусть R - число комнат, через которые необходимо пройти.

Пусть M(C,R) - минимальное число карточек, которое необходимо получить в автомате, чтобы пройти через R комнат, имея на руках не более C карточек в любой момент времени.

Например, M(3,6)=123 и M(4,6)=23.
Тогда ΣM(C,6)=146 для 3 ≤ C ≤ 4.

Дано, что ΣM(C,10)=10382 для 3 ≤ C ≤ 10.

Найдите ΣM(C,30) для 3 ≤ C ≤ 40.