아래 그림처럼 연속된 세 방이 자동문으로 연결돼 있습니다.

각 문은 보안 카드로 작동됩니다. 일단 한 방에 들어가면 문은 자동으로 닫히고 한번 사용한 보안 카드는 다시 사용할 수 없습니다. 시작(start) 방에 보안 카드를 무한히 발행하는 자판기가 있습니다만 (시작 방을 포함한) 각 방에 스캐너가 설치돼 있어 세 장이 넘는 보안 카드를 지니고 있거나 바닥에 보안 카드가 떨어져 있는 것이 감지되면 모든 문이 영구적으로 잠깁니다. 그러나, 각 방에는 다음 단계에서 사용할 보안 카드를 몇 장이고 안전하게 담아둘 수 있는 보관함이 있습니다.

만일 단순히 한번에 한방씩 지나가려고 한다면 3번 방에 들어갈 때 세 장의 보안 카드를 다 써버리게 되고 그 방에 영원히 갇히게 됩니다!

그러나, 각 방의 보관함을 잘 이용한다면 탈출할 수 있습니다. 예를 들어, 첫번째 카드로 1번 방에 들어가고, 카드 한장을 보관함에 둔 다음 세번째 카드를 써서 다시 시작 방으로 돌아갑니다. 그리고 다시 카드 자판기에서 세 장의 카드를 받아 1번 방에 들어가서 좀 전에 보관함에 넣어뒀던 카드를 다시 꺼냅니다. 이제 카드 세 장을 가지고 1번 방에 있으니 나머지 세 문을 통과할 수 있습니다. 이 방법을 쓰면 3개의 문을 총 6개의 보안 카드를 사용해서 통과할 수 있습니다.

최대 3장의 카드를 지닐 수 있다면 6개의 문을 통과하는데는 총 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) 값을 구하세요.