时空限制

1.5S/512M

题目描述

我的力量无人能及！

邪教徒拥有高达 $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$ 个回合结束后，邪教徒的血量仍然大于 $0$，则邪教徒会发动诸神之黄昏，机宝失败。

机宝希望取得胜利。在能够胜利的前提下，它希望自己的剩余血量尽可能多。

现在你需要操控机宝，求出机宝获胜时的最大剩余血量。

格式

输入格式

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

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

输出格式

输出一个整数。如果机宝能够击败邪教徒，输出获胜时的最大剩余血量；如果无法击败邪教徒，输出 -1。

样例

样例输入 #1

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

样例输出 #1

4

样例输入 #2

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

样例输出 #2

-1

样例解释 #2

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

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$	$HP\le$	其他限制
$1$	$20$	$8$	$10$	$hp, D, S \le 10$ 且 $u_i, v_i, k_i, w_i \le 10$
$2$	$20$	$2000$	$2000$	$k_i \le 2000$
$3$	$60$	$2 \times 10^5$	$10^{15}$	无

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$，$1 \le HP \le 10^{15}$，$1 \le hp \le 10^9$，$1 \le D, S \le 10^9$，对于任意 $1 \le i \le n$，有 $1 \le u_i, v_i, k_i, w_i \le 10^9$。