#!/usr/bin/env python3 def main(): n, c = (int(x) for x in input().split()) # We construct a DP table. Each index [i,j] represents the cost of finding # the boundary in that interval (including edges). We want to find the best # point to query. When querying we either get True or False. If we get True # we just found a non-strict upper bound for the boundary so the query costs # that index. If we get False we found a strict lower bound and the query # costs c. We want to consider the worst case so pick the maximum of the # two. We never need to query the nth index because it is guaranteed to be # True. dp = [[0] * n for _ in range(n)] for i in range(n): dp[i][i] = i + 1 for i in reversed(range(n)): for j in range(i + 1, n): dp[i][j] = min( max( # Too low (impossible if k = j because there is always a # valid value) dp[k + 1][j] + c if k < j else -1, # Too high dp[i][k - 1] + k + 1, # Correct guess dp[k][k], ) for k in range(i, j + 1) ) print(dp[0][-1]) if __name__ == "__main__": main()