多柱Hanoi塔问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

多柱Hanoi塔问题是3 柱Hanoi塔问题的推广。在一般情况下,给定p个塔座1,2,…,p。开始时,在塔座1 上有一叠共n 个圆盘,这些圆盘自下而上,由大到小地叠在一起。各圆盘从小到大编号为1,2,……,n。现要求将塔座1 上的这一叠圆盘移到塔座2上,并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则:
规则(1):每次只能移动1 个圆盘;
规则(2):任何时刻都不允许将较大的圆盘压在较小的圆盘之上;
规则(3):在满足移动规则(1)和(2)的前提下,可将圆盘移至1,2,…,p中任一塔座。
设计一个算法,计算完成所要求移动的最少移动次数。
对于给定的p个塔座和塔座1上的n个圆盘,计算将n个圆盘移到塔座2上需要的最少移动次数。

Input

输入数据的第1 行中的2 个正整数n和p分别表示有n个圆盘和p个塔座。n≤500,p≤20。

Output

将计算出的最少移动次数输出。

Sample Input

5 4

Sample Output

13

Hint

Source