Cyy有m种字符，编号为1到m，每用一个第i种字符需要的代价为i.他要使用这些字符来构造N个非空字符串，要求没有一个字符串是另一个字符串的前缀，现在他想知道最小的花费代价是多少。
输入有多组数据,不超过1000组. 每组数据第一行包含两个整数n和m.$(1\leq n\leq {10}^{9},2\leq m \leq {10}^{9})$
对于每组数据输出最小的花费.
1 2 3 2 5 2 1000 100000
1 7 17 10464
