终末对战

我的力量无人能及！

题目背景

终末祭坛上，邪教徒宣称自己拥有无人能及的力量。机宝虽然初始血量并不充裕，但它仍要在有限的回合内完成反击。

每一回合，机宝都能临时获得一批打击牌和防御牌。防御牌可以立刻抵挡本回合的攻击，而打击牌造成的伤害会在邪教徒攻击之后才结算。因此，机宝必须先活下来，才有机会用本回合的打击牌击败邪教徒。

题目描述

邪教徒初始有 $HP$ 点血量，机宝初始有 $hp$ 点血量。机宝需要在至多 $n$ 个回合内击败邪教徒。

在第 $i$ 个回合，会依次发生以下事件：

1. 机宝的手牌被清空，防御值重置为 $0$。
2. 机宝获得 $u_i$ 张打击牌和 $v_i$ 张防御牌，并从这些牌中选择至多 $k_i$ 张打出。
   • 每打出一张防御牌，机宝本回合的防御值立即增加 $D$。
   • 每打出一张打击牌，会在邪教徒攻击后对邪教徒造成 $S$ 点伤害。
3. 邪教徒发动攻击。若机宝当前防御值为 $y$，则机宝的血量减少 $\max(w_i-y,0)$。
4. 若机宝的血量小于等于 $0$，游戏立即结束，机宝失败。即使本回合的打击牌伤害足以击败邪教徒，也不会再结算。
5. 若机宝仍然存活，则结算本回合打击牌造成的伤害。若本回合机宝打出了 $x$ 张打击牌，则邪教徒血量减少 $xS$。
6. 若此时邪教徒的血量小于等于 $0$，游戏立即结束，机宝胜利。

如果 $n$ 个回合全部结束后邪教徒仍然存活，则邪教徒会发动诸神之黄昏，机宝失败。

机宝希望取得胜利。在能够胜利的前提下，它希望自己的剩余血量尽可能多。请你求出机宝获胜时的最大剩余血量。

输入格式

第一行包含五个正整数 $n,HP,hp,D,S$，分别表示最大回合数、邪教徒的初始血量、机宝的初始血量、每张防御牌提供的防御值以及每张打击牌造成的伤害。

接下来 $n$ 行，每行包含四个正整数 $u_i,v_i,k_i,w_i$，分别表示第 $i$ 个回合机宝获得的打击牌数量、防御牌数量、最多可以打出的牌数以及邪教徒本回合的攻击力。

输出格式

输出一个整数。

如果机宝能够击败邪教徒，输出获胜时的最大剩余血量；否则输出 -1。

样例 #1

样例输入 #1

3 15 10 3 5
2 2 2 5
1 2 2 4
2 1 2 6

样例输出 #1

4

样例解释 #1

一种可行但并非最优的策略如下：

• 第 $1$ 回合打出 $1$ 张防御牌和 $1$ 张打击牌，受到 $2$ 点伤害，并造成 $5$ 点伤害。
• 第 $2$ 回合打出 $1$ 张防御牌和 $1$ 张打击牌，受到 $1$ 点伤害，并造成 $5$ 点伤害。
• 第 $3$ 回合打出 $2$ 张打击牌，受到 $6$ 点伤害，并造成 $10$ 点伤害。

机宝最终剩余 $10-2-1-6=1$ 点血量。

一种最优策略是：前三回合都各打出 $1$ 张打击牌和 $1$ 张防御牌。三回合分别受到 $2,1,3$ 点伤害，并在第 $3$ 回合结算后击败邪教徒，最终剩余 $4$ 点血量。

样例 #2

样例输入 #2

2 100 10 5 2
1 1 1 10
1 1 1 10

样例输出 #2

-1

样例解释 #2

在两个回合内，机宝最多只能造成 $2\times 2=4$ 点伤害，无法击败血量为 $100$ 的邪教徒，因此输出 -1。

数据范围与子任务

注意：只有通过某个子任务的所有测试点，才能获得该子任务的分数。

对于所有测试数据，保证：

$$1\le n\le 2\times 10^5,\quad 1\le HP\le 10^{15},\quad 1\le hp,D,S\le 10^9,$$

且对于任意 $1\le i\le n$，有：

$$1\le u_i,v_i,k_i,w_i\le 10^9.$$

子任务编号	分数	限制
$1$	$20$	$n\le 8$，$HP\le 10$，且 $hp,D,S,u_i,v_i,k_i,w_i\le 10$
$2$		$n\le 2000$，$HP\le 2000$，且 $k_i\le 2000$
$3$	$60$	无额外限制