这是问题的困难版本。简单版本与困难版本的不同之处在于,它需要用最少的交易次数确定最小成本,而困难版本则需要用有限的交易次数确定最小成本。
狡猾的卖家卖掉了三个西瓜而不是一个后,他决定增加利润——也就是说,他买了更多的西瓜。现在他可以以 $$$3^{x+1} + x \cdot 3^{x-1}$$$ 的价格出售 $$$3^x$$$ 西瓜,其中 $$$x$$$ 是一个非负整数。这样的销售称为交易。
一位精于算计的买家来找他,但他时间不多,因此买家只能进行 $$$k$$$ 的交易,并计划购买 $$$n$$$ 西瓜。
买家很着急,因此请您确定如果他的交易不超过 $$$k$$$ 交易,他必须向卖家支付 $$$n$$$ 西瓜的最低硬币数量。如果不可能准确购买 $$$n$$$ 西瓜,同时进行不超过 $$$k$$$ 交易,则输出 $$$-1$$$。
输入
第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 10^4)$$$ — 测试用例的数量。每个测试用例的描述如下。
在每个测试用例的一行中,有两个整数 $$$n$$$ 和 $$$k$$$ $$$(1 \le n, k \le 10^9)$$$ — 需要购买多少个西瓜以及可以进行多少笔交易。
输出
对于每个测试用例,输出一个整数 - 西瓜的最低成本或 $$$-1$$$(如果不可能在满足所有条件的情况下购买西瓜)。
示例
输入复制
81 13 38 32 410 1020 143 29 1
输出复制
3 9 -1 6 30 63 10 33
注意
请注意,购买超出需要的西瓜是没有意义的,因此我们不会考虑西瓜数量超出需要的交易。
让我们考虑一下前两个交易选项的成本:
交易 A:$$$1$$$ 西瓜 — $$$3$$$ 硬币。
交易 B:$$$3$$$ 西瓜 — $$$10$$$ 硬币。
在第一个示例中,购买 $$$1$$$ 西瓜的唯一方法是使用交易 A,因此答案是 $$$3$$$。
在第二个示例中,您可以使用交易 B 以 $$$10$$$ 硬币购买 $$$3$$$ 西瓜,或者使用三个交易 A 以 $$$9$$$ 硬币购买 $$$3$$$ 西瓜,因此答案为 $$$9$$$。
在第三个示例中,$$$3$$$ 交易有以下选项:
$$$3$$$ 优惠 A — $$$3$$$ 西瓜。
$$$2$$$ 交易 A 和 $$$1$$$ 交易 B — $$$5$$$ 西瓜。
$$$1$$$ 交易 A 和 $$$2$$$ 交易 B — $$$7$$$ 西瓜。
$$$3$$$ 优惠 B — $$$9$$$ 西瓜。
可见是买不到的 正是 8 个西瓜。