题目描述

在六明文游戏中，玩家需要达成科技胜利条件：在 $t$ 回合内累计投入至少 $s$ 点科技点到科技胜利槽。

游戏中共有 $n$ 项科技。游戏初始时，只有第一项科技 $Tech_1$ 处于解锁状态并可被完成，其余科技均处于锁定状态。玩家必须按照$Tech_1→Tech_2→···→Tech_n$ 的固定顺序依次完成科技，不能跳过或改变顺序。具体而言，只有当玩家完成了前 $i−1$ 项科技（即 $Tech_1$ 至 $Tech_{i−1}$）后，第 $i$ 项科技 $Tech_i$ 才 会被解锁。

每项科技的完成都需要投入一定数量的科技点。玩家可以投入生产力来触发该科技的 “尤里卡” 时刻，以减少科技完成所需投入的科技点，每个科技的 “尤里卡” 时刻只能触发一次。完成科技后，玩家每回合获得的科技点将会增加。

每个科技 $Tech_i$ 有四个参数：

• $a_i$：完成此科技所需的科技点
• $k_i$：完成后每回合科技点的增量
• $b_i$：触发尤里卡所需的生产力
• $c_i$：触发尤里卡后可减少的科技点（$0⩽c_i<a_i$）

六明文是回合制游戏，每回合玩家先获得科技点和生产力，然后进行科技点和生产力的分配。科技点和生产力的分配必须是完整的（不能拆分到多个任务），且当前回合的科技点和生产力不会保存到下一回合。

游戏进程如下：

1. 在每个回合开始时，玩家获得：
   • 科技点 $m$（完成科技 $i$ 后，$m$ 永久增加 $k_i$）
   • 固定生产力 $p$（整场游戏保持不变）
2. 接着，玩家进行回合操作：

   • 科技点分配：

     (a) 将此回合获得的科技点 $m$ 完整投入到已解锁的科技或科技胜利槽。

     (b) 投入科技时，超出部分浪费，且不会用于完成下一个科技。完成第 $i$ 项科技 $Tech_i$ 后，$m$ 永久增加 $k_i$。

     (c) 投入科技胜利槽时直接累加。

   • 生产力分配：

     (a) 将此回合获得的生产力 $p$ 完整（不能拆分到多个科技尤里卡）投入到任意科技尤里卡（无论该科技是否已解锁）。

     (b) 投入科技尤里卡时，超出部分浪费。触发科技尤里卡后，可减少对应科技完成所需的科技点。

求最小的生产力 $p$（非负整数），使得存在一种操作策略，能在 $t$ 回合内达成科技胜利（科技胜利槽的科技点 $⩾s$）。若无法在 $t$ 回合内完成，输出 −1。

输入格式

第一行包含三个整数 $m,s, t（1⩽m⩽100, 1⩽s⩽10^9, 1⩽t⩽100）$。

第二行包含一个整数 $n（0⩽n⩽100）$。

接下来 n 行，每行包含四个整数 $a_i, k_i, b_i, c_i（1 ⩽ a_i ⩽ 10^6, 0 ⩽ k_i ⩽ 1000, 1 ⩽ b_i ⩽ 10000, 0 ⩽ci <ai）$。

输出格式

输出最小生产力 $p$（非负整数）。若无法在 $t$ 回合内完成，输出 −1。

10 100 9
2
50 10 20 25
60 10 30 20

4

解释 #1

样例中，$p = 4$ 的合法策略如下：

• 回合 1：获得 $10$ 科技点和 $4$ 生产力。将生产力分配给 $Tech_1$ 的尤里卡，科技点分配给 $Tech_1$。
• 回合 2：获得 $10$ 科技点和 $4$ 生产力。将生产力分配给 $Tech_1$ 的尤里卡，科技点分配给 $Tech_1$。
• 回合 3：获得 $10$ 科技点和 $4$ 生产力。将生产力分配给 $Tech_1$ 的尤里卡，科技点分配给 $Tech_1$。
• 回合 4：获得 $10$ 科技点和 $4$ 生产力。将生产力分配给 $Tech_1$ 的尤里卡，科技点分配给科技胜利槽。
• 回合 5：获得 $10$ 科技点和 $4$ 生产力。将生产力分配给 $Tech_1$ 的尤里卡，科技点分配给科技胜利槽。在这个回合，$Tech1$ 的尤里卡已累计获得 $20$ 生产力，触发了尤里卡。$Tech_1$ 现在完成需要的科技点是 $50−25 = 25$。由于已经分配了 $30$ 点科技点，$Tech_1$ 研究完成。每回合获得的科技点增加到 $10+10=20$。
• 回合 6：获得 $20$ 科技点和 $4$ 生产力。将科技点分配给科技胜利槽。
• 回合 7：获得 $20$ 科技点和 $4$ 生产力。将科技点分配给科技胜利槽。
• 回合 8：获得 $20$ 科技点和 $4$ 生产力。将科技点分配给科技胜利槽。
• 回合 9：获得 $20$ 科技点和 $4$ 生产力。将科技点分配给科技胜利槽。科技胜利槽总共积累了 $10 (T4) + 10 (T5) + 20 (T6) + 20 (T7) + 20 (T8) + 20 (T9) = 100$ 点科技点。达成科技胜利！

22 970 8
3
85 24 9 27
81 20 85 44
30 80 75 7

-1