# 战斗属性的升级计划

预估时间限制：3 秒。内存限制：512 MB。

实际时限以标准程序在目标环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

远征队要依次通过一组守卫。工坊提供三种属性升级，队长希望用最少的徽章保证队员在全部战斗后仍然存活。

(本故事由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

### 输入

```text
1
10 5 7
7 3 1 2 9
6 8 7 1
```

### 输出

```text
2
10 5 16
```

### 样例 2

### 输入

```text
1
1 1 2
1 1 1 1 1
1 1 1 2
```

### 输出

```text
1
1 2 2
```

### 样例 3

### 输入

```text
1
4 8 2
2 3 1 4 3
2 4 7 5
```

### 输出

```text
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% | 无额外条件 |