有一天 wrzSama 在寻宝，突然他掉到了一个神奇的房间里。这个房间里有 nn 个机器，第 ii 个机器可以生产 2^i2 i 个钻石。 具体地，wrzSama 可以用 a_ia i ​ 的时间开动第 ii 个机器，让它生产 2^i2 i 个钻石。这些机器有个很特殊的性质，每当他用一次第 ii 个机器后，会让它的开动时间 a_ia i ​ 加上 b_ib i ​ 。这意味着当他要第二次得到这 2^i2 i 个钻石时就需要 a_i + b_ia i ​ +b i ​ 的时间，每次不断累加，第 xx 次开动就需要 a_i+(x-1)b_ia i ​ +(x−1)b i ​ 的时间。 wrzSama 需要得到至少 2^n2 n 个钻石来得到宝藏，请问他最少需要多长时间

根据题意，wrzSama 需要得到至少 2^n2 n 个钻石来得到宝藏，那么他需要开动第 n 个机器，即生产 2^n2 n 个钻石。由于每次开动第 ii 个机器需要的时间为 a_i (x-1)b_ia i ​ (x−1)b i ​ ，那么开动第 n 个机器一次需要的时间为 a_n b_nb n ​ ，开动两次需要的时间为 a_n (2-1)b_na n ​ (2−1)b n ​ ，以此类推，开动 x 次需要的时间为 a_n (x-1)b_na n ​ (x−1)b n ​ 。因此，wrzSama 需要开动第 n 个机器 x 次，使得 2^n2 n ≤ 2^i2 i 的总和，即：

2^n ≤ 2^1 + 2^2 + ... + 2^{n-1} + 2^n

化简得：

2^n ≤ 2^{n+1} - 2

移项得：

2^{n+1} ≥ 2^n + 2

因此，wrzSama 需要开动第 n 个机器至少 x = ⌈log_2(n+2)⌉ 次，其中 ⌈x⌉ 表示不小于 x 的最小整数。因此，wrzSama 最少需要的时间为：

a_n + a_n b_n + a_n 2b_n + ... + a_n (x-1)b_n

化简得：

a_n(2^x - 1) + b_n(1 + 2 + ... + (x-1))

因此，wrzSama 最少需要的时间为：

a_n(2^⌈log_2(n+2)⌉ - 1) + b_n(1 + 2 + ... + ⌈log_2(n+2)⌉-1)

注意到 1 + 2 + ... + k = k(k+1)/2，因此可以进一步化简得：

wrzSama 最少需要的时间为：

a_n(2^⌈log_2(n+2)⌉ - 1) + b_n⌈log_2(n+2)⌉(⌈log_2(n+2)⌉-1)/2

因此，以上就是 wrzSama 最少需要的时间的计算方法。