题意

有 $n$ 条巨龙，按顺序杀。
每条龙 $i$ 有：

• 生命值 $a_i$
• 恢复力 $p_i$
• 杀死后获得一把新剑（攻击力 $w_i$）

玩家初始有 $m$ 把剑（攻击力已知）。
打每条龙时：

1. 选剑规则：选攻击力 $\le a_i$ 的最大攻击力剑，若没有则选最小攻击力剑。
2. 用该剑攻击 $x$ 次（固定的 $x$），每次伤害 = 剑的攻击力。
3. 攻击后龙的生命变化：$a_i \to a_i - x \times \text{ATK}$，若此时 $\le 0$，则恢复，每次恢复 $p_i$，直到生命值 $\ge 0$。
4. 必须最终生命值 恰好为 0 才死。

求能通关所有龙的 最小正整数 $x$，不存在输出 $-1$。

---

问题分析

1. 选剑的确定

由于剑的选择规则固定，且每次杀龙后剑会变化（消失一把，获得一把），我们可以预先模拟整个过程的选剑结果。

设 $\text{ATK}_i$ 表示打第 $i$ 条龙时使用的剑的攻击力。

模拟方法：

• 用平衡树（如 std::multiset）维护当前拥有的剑。
• 对于龙 $i$：
  • 在平衡树中找 $\le a_i$ 的最大元素（可用 upper_bound(a_i) 前一个元素），如果不存在则取最小元素（begin()）。
  • 使用该剑，从平衡树中删除它。
  • 加入杀死该龙获得的剑 $w_i$。

这样我们得到序列 $\{\text{ATK}_i\}$。

---

2. 转化为同余方程

对于第 $i$ 条龙，攻击 $x$ 次后，造成的伤害是 $x \cdot \text{ATK}_i$。

攻击后生命值：

$$\text{剩余} = a_i - x \cdot \text{ATK}_i$$

龙恢复 $k_i$ 次（$k_i \ge 0$）后生命值恰好为 $0$，即：

$$a_i - x \cdot \text{ATK}_i + k_i \cdot p_i = 0$$

整理得：

$$x \cdot \text{ATK}_i \equiv a_i \pmod{p_i}$$

并且需要满足：

$$x \cdot \text{ATK}_i \ge a_i \quad\text{(因为恢复前生命值要 ≤ 0)} $$

---

3. 同余方程标准化

方程：

$$\text{ATK}_i \cdot x \equiv a_i \pmod{p_i}$$

设 $d_i = \gcd(\text{ATK}_i, p_i)$。

若 $d_i \nmid a_i$，则无解，直接输出 $-1$。

否则令：

$$A_i = \frac{\text{ATK}_i}{d_i}, \quad B_i = \frac{a_i}{d_i}, \quad P_i = \frac{p_i}{d_i} $$

方程化为：

$$A_i \cdot x \equiv B_i \pmod{P_i}$$

由于 $\gcd(A_i, P_i) = 1$，可求 $A_i$ 在模 $P_i$ 下的逆元 $A_i^{-1}$，得到：

$$x \equiv B_i \cdot A_i^{-1} \pmod{P_i}$$

设：

$$x \equiv r_i \pmod{P_i}$$

其中 $r_i = (B_i \cdot A_i^{-1}) \bmod P_i$。

---

4. 合并同余方程

现在我们得到若干方程：

$$x \equiv r_1 \pmod{P_1}$$ $$x \equiv r_2 \pmod{P_2}$$

...

$$x \equiv r_n \pmod{P_n}$$

用 扩展中国剩余定理 (ExCRT) 合并这些方程。

ExCRT 合并两个方程：

$$x \equiv r_1 \pmod{m_1}$$ $$x \equiv r_2 \pmod{m_2}$$

设 $x = r_1 + t \cdot m_1$，代入第二式：

$$r_1 + t \cdot m_1 \equiv r_2 \pmod{m_2}$$ $$m_1 \cdot t \equiv r_2 - r_1 \pmod{m_2}$$

设 $d = \gcd(m_1, m_2)$，若 $d \nmid (r_2 - r_1)$ 则无解。
否则化为：

$$\frac{m_1}{d} \cdot t \equiv \frac{r_2 - r_1}{d} \pmod{\frac{m_2}{d}} $$

解出 $t \equiv t_0 \pmod{\frac{m_2}{d}}$，即 $t = t_0 + k \cdot \frac{m_2}{d}$。

代回得：

$$x = r_1 + m_1 \cdot \left(t_0 + k \cdot \frac{m_2}{d}\right) = (r_1 + m_1 \cdot t_0) + k \cdot \frac{m_1 m_2}{d} $$

所以新方程：

$$x \equiv r_1 + m_1 \cdot t_0 \pmod{\mathrm{lcm}(m_1, m_2)} $$

重复合并直到所有方程合并成一个 $x \equiv R \pmod{M}$。

---

5. 处理攻击力下限条件

我们还有条件：

$$x \cdot \text{ATK}_i \ge a_i$$

即：

$$x \ge \lceil \frac{a_i}{\text{ATK}_i} \rceil$$

设：

$$L = \max_{i=1}^n \left\lceil \frac{a_i}{\text{ATK}_i} \right\rceil $$

最终 $x$ 必须 $\ge L$ 且满足同余方程 $x \equiv R \pmod{M}$。

---

6. 求解最小正整数解

设最终合并为：

$$x \equiv R \pmod{M}$$

最小非负解是 $x_0 = R \bmod M$（调整为 $[0, M)$ 范围内）。

如果 $x_0 \ge L$，则答案为 $x_0$。
否则，需要找到最小的 $x \ge L$ 且 $x \equiv R \pmod{M}$：

$$x = x_0 + k \cdot M \ge L$$ $$k \ge \frac{L - x_0}{M}$$

取 $k = \lceil (L - x_0) / M \rceil$（如果 $L > x_0$），则：

$$x = x_0 + k \cdot M$$

---

算法步骤

1. 读入数据。
2. 用 multiset 模拟选剑过程，得到 $\text{ATK}_i$。
3. 对每条龙：
   • 检查 $\gcd(\text{ATK}_i, p_i) \mid a_i$，否则输出 $-1$。
   • 标准化方程，得到 $x \equiv r_i \pmod{P_i}$。
4. 用 ExCRT 合并所有同余方程，得到 $x \equiv R \pmod{M}$。
5. 计算 $L = \max \lceil a_i / \text{ATK}_i \rceil$。
6. 找最小 $x \ge L$ 满足同余式。
7. 输出结果。

---

时间复杂度

• 模拟选剑：$O((n + m) \log m)$
• ExCRT：$O(n \log (\max p_i))$
• 总体可行。

---

样例验证

以第一组数据为例：

输入：

3 3
3 5 7
4 6 10
7 3 9
1 9 1000

模拟选剑：

• 龙1: $a=3$，剑 {1,9,1000}，选1，得新剑7 → {7,9,1000}
• 龙2: $a=5$，选7，得新剑3 → {3,9,1000}
• 龙3: $a=7$，选3，得新剑9 → {9,9,1000}

所以 ATK = [1, 7, 3]。

解方程：

• 龙1: $1 \cdot x \equiv 3 \pmod{4}$ → $x \equiv 3 \pmod{4}$
• 龙2: $7 \cdot x \equiv 5 \pmod{6}$ → $x \equiv 5 \pmod{6}$
• 龙3: $3 \cdot x \equiv 7 \pmod{10}$ → $x \equiv 9 \pmod{10}$

合并：

1. $x \equiv 3 \pmod{4}$ 与 $x \equiv 5 \pmod{6}$
   解 $t$: $4t \equiv 2 \pmod{6}$ → $2t \equiv 1 \pmod{3}$ → $t \equiv 2 \pmod{3}$
   $x = 3 + 4 \cdot 2 = 11 \pmod{12}$ → $x \equiv 11 \pmod{12}$

2. $x \equiv 11 \pmod{12}$ 与 $x \equiv 9 \pmod{10}$
   解 $t$: $12t \equiv -2 \pmod{10}$ → $2t \equiv 8 \pmod{10}$ → $t \equiv 4 \pmod{5}$
   $x = 11 + 12 \cdot 4 = 59 \pmod{60}$ → $x \equiv 59 \pmod{60}$

$L = \max(\lceil 3/1 \rceil, \lceil 5/7 \rceil, \lceil 7/3 \rceil) = \max(3, 1, 3) = 3$
$59 \ge 3$，所以答案是 $59$，符合样例。

---

代码实现注意事项

• 使用 multiset 维护剑的集合。
• 注意选剑规则：upper_bound 前一个元素。
• 大数运算使用 long long，乘法可能溢出，要用快速乘或 __int128。
• 检查无解情况：① 同余方程无解 ② 逆元不存在（但这里标准化后互质，一定有逆元）③ 恢复前生命值不能 >0 的情况已在 $L$ 中处理。