CF2132C2.The Cunning Seller (hard version)

这是该问题的困难版本。简单版本与困难版本的区别在于，简单版本要求用最少的交易次数获得最小花费，而困难版本要求在限定的交易次数内获得最小花费。

在狡猾的商贩卖出三只西瓜而不是一只之后，他决定进一步增加利润——也就是说，他买了更多的西瓜。现在他可以用一次交易卖出 $3^x$ 个西瓜，售价为 $3^{x+1} + x \cdot 3^{x-1}$ 枚硬币，其中 $x$ 是非负整数。这样的售卖方式称为一次“交易”。

一位精明的买家来找他，但买家的时间有限，因此最多只能进行 $k$ 次交易，并且计划恰好购买 $n$ 个西瓜。

由于买家很着急，因此他请求你帮忙计算：如果最多只能进行 $k$ 次交易，买下 $n$ 个西瓜所需支付的最少硬币数是多少。如果无法在不超过 $k$ 次交易的情况下恰好买到 $n$ 个西瓜，则输出 $-1$。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来每个测试用例占一行，每行包含两个整数 $n$ 和 $k$（$1 \le n, k \le 10^9$），分别表示需要购买的西瓜数量和最多允许的交易次数。

对于每个测试用例，输出一个整数，表示买下 $n$ 个西瓜所需支付的最少硬币数。如果无法满足条件，输出 $-1$。

注意，没有必要购买多于所需数量的西瓜，因此我们不会考虑那些买的西瓜数量超过需求的交易。

我们来看前两种交易方式的花费：

交易 A：$1$ 个西瓜——$3$ 枚硬币。

交易 B：$3$ 个西瓜——$10$ 枚硬币。

在第一个样例中，唯一的方式是用交易 A 买 $1$ 个西瓜，因此答案是 $3$。

在第二个样例中，可以用交易 B 买 $3$ 个西瓜，花费 $10$ 枚硬币，也可以用三次交易 A 买 $3$ 个西瓜，花费 $9$ 枚硬币，因此答案是 $9$。

在第三个样例中，以下是 $3$ 次交易的所有可能：

$3$ 次交易 A——$3$ 个西瓜。

$2$ 次交易 A 和 $1$ 次交易 B——$5$ 个西瓜。

$1$ 次交易 A 和 $2$ 次交易 B——$7$ 个西瓜。

$3$ 次交易 B——$9$ 个西瓜。

可以看出，无法恰好买到 $8$ 个西瓜。

由 ChatGPT 4.1 翻译