战斗属性的升级计划¶
预估时间限制：3 秒。内存限制：512 MB。
实际时限以标准程序在目标环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。
背景故事¶
远征队要依次通过一组守卫。工坊提供三种属性升级，队长希望用最少的徽章保证队员在全部战斗后仍然存活。
(本故事由GPT-6重写)
形式化问题描述¶
角色初始生命、防御、攻击分别为 \(H_0,D_0,A_0\) .有 \(n\) 种敌人，第 \(i\) 种有 \(k_i\) 个，每个敌人的初始生命、防御、攻击为 \(h_i,d_i,a_i\) .
每次与一个敌人战斗。双方每回合同时攻击：攻击高于对方防御时，对方生命减少攻击与防御的差；否则造成零伤害。每回合后，若至少一方生命不大于零，战斗结束。生命不大于零的一方失败；同时不大于零则双方都失败。角色在战斗之间不恢复生命，每个新敌人以初始生命进入战斗。
战斗开始前可以任意次进行以下升级：
- 花费 \(C_H\) 枚徽章，生命增加 \(1\) ；
- 花费 \(C_D\) 枚徽章，防御增加 \(V_D\) ；
- 花费 \(C_A\) 枚徽章，攻击增加 \(V_A\) .
击败全部 \(\sum_i k_i\) 个敌人，并保证最终生命严格为正。求最小花费，以及升级完成、尚未战斗时的属性 \((H,D,A)\) .多个最优方案按 \(H\) 、\(D\) 、\(A\) 顺序比较，输出字典序最小的三元组。
输入格式¶
第一行一个整数 \(n\) .第二行三个整数 \(H_0,D_0,A_0\) .第三行五个整数 \(C_H,C_D,V_D,C_A,V_A\) .接下来 \(n\) 行，每行四个整数 \(k_i,h_i,d_i,a_i\) .
输出格式¶
若无法完成，输出一行 \(-1\) .否则第一行输出最小花费，第二行输出 \(H,D,A\) .本题所有步长均为正，总能找到可行方案。
样例¶
样例 1¶
输入¶
1
10 5 7
7 3 1 2 9
6 8 7 1
输出¶
2
10 5 16
样例 2¶
输入¶
1
1 1 2
1 1 1 1 1
1 1 1 2
输出¶
1
1 2 2
样例 3¶
输入¶
1
4 8 2
2 3 1 4 3
2 4 7 5
输出¶
8
4 8 8
样例解释¶
样例一花费 \(2\) ，将攻击从 \(7\) 升至 \(16\) ，便可无伤击败所有敌人。样例二加一点生命或一点防御都只需 \(1\) ；升级后生命更小的 \((1,2,2)\) 胜出。样例三敌人不能造成伤害，但角色的攻击仍须高于敌人防御，最便宜的结果是攻击 \(8\) ，花费 \(8\) .
数据范围与保证¶
\(1\le n,k_i\le5000\) .初始属性、敌人属性和两个升级步长均在 \(1,\ldots,5000000\) 内；\(1\le C_H,C_D,C_A\le1000000000\) .输入均为整数。
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |