C2. 狡猾的卖家（困难版）

题目描述

这是该题的困难版本。简单版本与困难版本的区别在于：简单版本要求在交易次数最少的前提下求最小花费，而困难版本要求在交易次数不超过 k 的前提下求最小花费。

狡猾的卖家之前成功把一个西瓜当成三个卖掉后，决定进一步提高利润——他进了更多西瓜。现在，他可以以 3^(x+1) + x*3^(x-1) 枚硬币的价格出售 3^x 个西瓜（其中 x 是非负整数）。这样的一次销售称为一笔交易。

一位精打细算的买家前来购买，但他时间有限，最多只能进行 k 笔交易，且计划恰好购买 n 个西瓜。

买家很着急，于是向你求助：请计算他在不超过 k 笔交易的前提下，购买恰好 n 个西瓜所需支付的最少硬币数。如果无法在不超过 k 笔交易的情况下恰好买到 n 个西瓜，输出 -1。

输入格式

第一行包含一个整数 t（1 ≤ t ≤ 1e4）——测试用例的数量。 每个测试用例占一行，包含两个整数 n 和 k（1 ≤ n, k ≤ 1e9）——分别表示需要购买的西瓜数量和最多可进行的交易次数。

输出格式

对于每个测试用例，输出一个整数——购买恰好 n 个西瓜的最小花费；如果无法满足条件，输出 -1。

样例输入

8
1 1
3 3
8 3
2 4
10 10
20 14
3 2
9 1

样例输出

3
9
-1
6
30
63
10
33

提示

注意，购买超过所需数量的西瓜是没有意义的，因此我们不考虑交易后西瓜总数超过 n 的情况。

以下是前两种交易方式的详细说明：

• 交易 A（x=0）：1 个西瓜，花费 3 枚硬币。
• 交易 B（x=1）：3 个西瓜，花费 10 枚硬币。

样例 1 解释：购买 1 个西瓜的唯一方式是使用交易 A，因此答案为 3。 样例 2 解释：购买 3 个西瓜有两种选择：使用 1 笔交易 B（花费 10 枚硬币），或使用 3 笔交易 A（花费 3×3=9 枚硬币），因此最小花费为 9。 样例 3 解释：3 笔交易的所有可能组合如下：

• 3 笔交易 A：共 3 个西瓜。
• 2 笔交易 A + 1 笔交易 B：共 2×1 + 1×3=5 个西瓜。
• 1 笔交易 A + 2 笔交易 B：共 1×1 + 2×3=7 个西瓜。
• 3 笔交易 B：共 3×3=9 个西瓜。 无法恰好买到 8 个西瓜，因此输出 -1。