# Problem 327

**Rooms of Doom**

A series of three rooms are connected to each other by automatic doors.

Each door is operated by a security card. Once you enter a room the door automatically closes and that security card cannot be used again. A machine at the start will dispense an unlimited number of cards, but each room (including the starting room) contains scanners and if they detect that you are holding more than three security cards or if they detect an unattended security card on the floor, then all the doors will become permanently locked. However, each room contains a box where you may safely store any number of security cards for use at a later stage.

If you simply tried to travel through the rooms one at a time then as you entered room 3 you would have used all three cards and would be trapped in that room forever!

However, if you make use of the storage boxes, then escape is possible. For example, you could enter room 1 using your first card, place one card in the storage box, and use your third card to exit the room back to the start. Then after collecting three more cards from the dispensing machine you could use one to enter room 1 and collect the card you placed in the box a moment ago. You now have three cards again and will be able to travel through the remaining three doors. This method allows you to travel through all three rooms using six security cards in total.

It is possible to travel through six rooms using a total of 123 security cards while carrying a maximum of 3 cards.

Let C be the maximum number of cards which can be carried at any time.

Let R be the number of rooms to travel through.

Let M(C,R) be the minimum number of cards required from the dispensing machine to travel through R rooms carrying up to a maximum of C cards at any time.

For example, M(3,6)=123 and M(4,6)=23.

And, ΣM(C,6)=146 for 3 ≤ C ≤ 4.

You are given that ΣM(C,10)=10382 for 3 ≤ C ≤ 10.

Find ΣM(C,30) for 3 ≤ C ≤ 40.

**命运房间**

有三个房间，相互之间由自动门相连接。

（左：初始房间；右：结束房间）

每扇门可以用安保卡操作。一旦你打开门进入房间，门会自动关闭，所使用的安保卡将失效。在初始位置有一台分发机能够提供无限量的安保卡，但每一间房间（包括初始房间）中都安装有扫描器，如果它们检测到你持有多于三张有效安保卡，或者在地上发现了无主的有效安保卡，所有的门将会永久上锁。不过，每个房间中提供了一个箱子，你可以在其中储存任意数量的安保卡，以供后用。

如果你试图直接穿过所有的门，当你进入第3个房间时，你就会用完所有3张安保卡，然后永远地陷在这个房间里！

不过，如果你利用储存箱，想要逃到结束房间还是很容易的。例如，你可以先用第一张安保卡进入第1个房间，放一张安保卡在储存箱里，然后用第三张安保卡回到初始房间。然后，从分发机中再取出三张安保卡，用一张进入第1个房间，再取走之前放入储存箱的那张安保卡，这样你就又有了三张安保卡，可以穿过剩下的三道门。这个方法使得你可以使用总计六张安保卡通过全部三个房间。

当携带上限为3张安保卡时，通过六个房间最少需要总计123张安保卡。

记C是安保卡的携带上限。

记R是要通过的房间数目。

记M(C,R)为当携带上限为C张安保卡时，通过R个房间最少需要从分发机中取出的安保卡数目。

例如， M(3,6)=123以及M(4,6)=23。

进而对于3 ≤ C ≤ 4，ΣM(C,6)=146。

已知对于3 ≤ C ≤ 10，ΣM(C,10)=10382。

对于3 ≤ C ≤ 40，求ΣM(C,30)。