题解：最小花费购买皮肤方案

问题转化

有 $N$ 个英雄，英雄 $i$ 有 $K_i$ 款皮肤，每款价格 $C_i$。如果给英雄 $i$ 购买了 $b_i$ 款皮肤（$0 \le b_i \le K_i$），则展示策略数为：

$$\prod_{i=1}^N b_i$$

需要满足：

$$\prod_{i=1}^N b_i \ge M$$

总花费为：

$$\sum_{i=1}^N b_i \times C_i$$

求最小总花费。

约束条件

• $M \le 10^{17}$（极大）
• $K_i \le 10$，$C_i \le 199$
• $N \le \max(5, (\log_2 i)^4)$，最大 $N \approx 16$（因为 $(\log_2 10)^4 \approx 33$，但实际通常更小）

动态规划思路

1. 状态设计

由于 $M$ 很大但 $N$ 很小，且 $b_i \le 10$，考虑 DP 状态为已经考虑了前 $i$ 个英雄，当前乘积为 $p$ 的最小花费。

但 $p$ 可能达到 $10^{17}$ 太大，需要压缩。

2. 乘积压缩

注意到 $M \le 10^{17}$，如果乘积已经 $\ge M$，可以直接视为 $M$，因为更大的乘积不会让花费更小（价格非负）。

因此定义 $dp[i][p]$ 表示考虑前 $i$ 个英雄，当前乘积为 $p$（但 $p \le M$）的最小花费。当 $p \ge M$ 时统一记作 $M$。

由于 $N$ 很小，状态数可控。

3. 转移方程

初始化 $dp[0][1] = 0$，其他 $dp[0][*] = \infty$。

对于英雄 $i$：

$$dp[i][\min(M, p \times b)] = \min(dp[i][\min(M, p \times b)],\ dp[i-1][p] + b \times C_i) $$

其中 $b = 0,1,\dots,K_i$，但注意 $b=0$ 时乘积为 0，不合法（因为最终乘积至少为 $1$ 才能大于等于 $M$ 当 $M=1$）。实际上我们不允许 $b=0$，因为题目要求“只玩有皮肤的英雄”，所以 $b_i \ge 1$。

但样例中英雄皮肤数可以为 $0$，意思是如果 $K_i=0$ 则不能选该英雄展示？不，题目说“对于有皮肤的每一个英雄”，所以如果 $K_i=0$ 则该英雄不能选（即 $b_i=0$），但此时展示策略数会乘以 $0$，因此必须所有英雄 $b_i \ge 1$ 才有效。

所以约束：$1 \le b_i \le K_i$。

4. 状态数量优化

$M$ 最大 $10^{17}$，但 $N \le 16$，每个 $b_i \le 10$，总乘积可能非常大，但超过 $M$ 后统一记为 $M$。

因此 $p$ 的可能取值是由若干个不超过 $10$ 的数相乘得到，且不超过 $M$。这样的数不会太多（本质是 $M$ 以内形如 $2^a 3^b 5^c 7^d$ 的数）。

实际上，$M \le 10^{17}$，因子只有 $2,3,5,7$（因为 $b_i \le 10$，可能的质因子只有 $2,3,5,7$）。

估算状态数：设 $p = 2^a 3^b 5^c 7^d$，且 $p \le M$。
$a \le \lfloor \log_2 M \rfloor \le 57$，
$b \le \lfloor \log_3 M \rfloor \le 36$，
$c \le \lfloor \log_5 M \rfloor \le 24$，
$d \le \lfloor \log_7 M \rfloor \le 19$。

理论最大状态数约 $58\times 37\times 25\times 20 \approx 1.07\times 10^6$，但实际小得多，因为乘积增长快。

5. 使用哈希表存储状态

用 unordered_map 存储 dp 状态：key = 乘积 $p$，value = 最小花费。
每次转移时枚举 $b_i$，更新新乘积对应的最小花费。

6. 算法步骤

1. 读入 $N, M, K_i, C_i$
2. 初始化 dp 字典：dp[1] = 0（乘积为 1 花费 0）
3. 对每个英雄 $i$：
   • 创建新字典 ndp
   • 遍历 dp 中每个状态 (prod, cost)
   • 枚举 $b = 1$ 到 $K_i$：
     • 新乘积 new_prod = prod * b
     • 如果 new_prod >= M，令 new_prod = M
     • 新花费 new_cost = cost + b * C_i
     • 更新 ndp[new_prod] = min(ndp[new_prod], new_cost)
   • dp = ndp
4. 答案 = dp[M]（因为最后乘积至少为 M）

7. 复杂度分析

• 状态数约 $10^5$ 量级
• 每个状态枚举 $b_i \le 10$，转移 $O(10)$
• 总复杂度 $O(10 \times N \times \text{状态数})$，可过

8. 特例处理

• 若 $M=1$，则答案为 $\sum_{i=1}^N C_i$（每个英雄买 1 款皮肤）
• 若有 $K_i=0$ 的英雄，则无解（但题目保证有解）

最终答案

输出 dp[M] 即可。