题目描述

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

游戏中共有 $n$ 项科技。游戏初始时，只有第一项科技 $\mathrm{Tech}_1$ 处于解锁状态并可被完成，其余科技均处于锁定状态。玩家必须按照 $\mathrm{Tech}_1 \to \mathrm{Tech}_2 \to \cdots \to \mathrm{Tech}_n$ 的固定顺序依次完成科技，不能跳过或改变顺序。只有当玩家完成了前 $i-1$ 项科技（即 $\mathrm{Tech}_1$ 至 $\mathrm{Tech}_{i-1}$）后，第 $i$ 项科技 $\mathrm{Tech}_i$ 才会被解锁。

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

每个科技 $\mathrm{Tech}_i$ 有四个参数：

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

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

游戏进程如下：

1. 在每个回合开始时，玩家获得：

   • 科技点 $m$（完成科技 $i$ 后，$m$ 永久增加 $k_i$）；
   • 固定生产力 $p$（整场游戏保持不变）。

2. 接着，玩家进行回合操作：

   科技点分配

   • 将此回合获得的科技点 $m$ 完整投入到已解锁的科技或科技胜利槽。
   • 投入科技时，超出部分浪费，且不会用于完成下一个科技。完成第 $i$ 项科技 $\mathrm{Tech}_i$ 后，$m$ 永久增加 $k_i$。
   • 投入科技胜利槽时直接累加。

   生产力分配

   • 将此回合获得的生产力 $p$ 完整（不能拆分到多个科技尤里卡）投入到任意科技尤里卡（无论该科技是否已解锁）。
   • 投入科技尤里卡时，超出部分浪费。触发科技尤里卡后，可减少对应科技完成所需的科技点（减少量为 $c_i$）。

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

输入格式

• 第一行：三个整数 $m\ s\ t$，分别表示初始每回合科技点产出 $m$、胜利槽目标 $s$、允许的最多回合数 $t$。
• 第二行：整数 $n$，表示科技数目。
• 接下来 $n$ 行：第 $i$ 行包含四个整数 $a_i\ k_i\ b_i\ c_i$，对应第 $i$ 项科技的参数，其中：
  • $a_i$：完成该科技所需的科技点；
  • $k_i$：完成后每回合科技点增量；
  • $b_i$：触发尤里卡所需的生产力；
  • $c_i：触发尤里卡后可减少的科技点（满足 0 \le c_i < a_i$）。

输入按行、以空格分隔，严格按上述顺序给出，所有值为非负整数。

输出格式

输出一个整数 —— 满足条件的最小非负整数生产力 $p$。如果不存在使得在不超过 $t$ 回合内达到科技胜利的方法，输出$-1$。

输入输出样例 #1

输入 #1

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

输出 #1

4

输入输出样例 #2

输入 #2

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

输出 #2

-1

说明/提示

对于第$1$组样例：

• 回合 1：获得 $10$ 科技点和 $4$ 生产力。将生产力分配给 $\mathrm{Tech}_1$ 的尤里卡，科技点分配给 $\mathrm{Tech}_1$（累计科技点：$10$）。

• 回合 2：获得 $10$ 科技点和 $4$ 生产力。将生产力继续投入 $\mathrm{Tech}_1$ 的尤里卡，科技点继续投入 $\mathrm{Tech}_1$（累计投入：$10+10=20$）。

• 回合 3：获得 $10$ 科技点和 $4$ 生产力。生产力继续投入 $\mathrm{Tech}_1$ 的尤里卡，科技点继续投入 $\mathrm{Tech}_1$（累计投入：$10+10+10=30$）。

• 回合 4：获得 $10$ 科技点和 $4$ 生产力。生产力继续投入 $\mathrm{Tech}_1$ 的尤里卡，科技点投入到科技胜利槽（胜利槽累计：$10$）。此前对 $\mathrm{Tech}_1$ 的累计投入仍为 $30$。

• 回合 5：获得 $10$ 科技点和 $4$ 生产力。生产力继续投入 $\mathrm{Tech}_1$ 的尤里卡，科技点再投入到科技胜利槽（胜利槽累计：$10+10=20$）。

  此时 $\mathrm{Tech}_1$ 的尤里卡累计生产力为 $4\times5=20 \ge b_1=20$，触发尤里卡，使需求变为
  $a_1 - c_1 = 50 - 25 = 25.$
  由于已累计投入科技点 $30 \ge 25$，$\mathrm{Tech}_1$ 完成，产出增加 $k_1=10$，即每回合科技点从 $10$ 变为
  $10+10=20.$

• 回合 6：获得 $20$ 科技点和 $4$ 生产力。将科技点投入到科技胜利槽（累计：$20+20=40$）。

• 回合 7：获得 $20$ 科技点和 $4$ 生产力。将科技点投入到科技胜利槽（累计：$40+20=60$）。

• 回合 8：获得 $20$ 科技点和 $4$ 生产力。将科技点投入到科技胜利槽（累计：$60+20=80$）。

• 回合 9：获得 $20$ 科技点和 $4$ 生产力。将科技点投入到科技胜利槽（累计：$80+20=100$）。

因此在上述策略下，$p=4$ 是可行的，满足在不超过 $9$ 回合内使胜利槽达到目标 $s=100$。可以证明不存在$<4$的答案。