P14442 [JOISC 2013] 礼物 / Presents

JOI 学园每年在白色情人节期间会举行点心交换会。今年的交换会有 $N$ 名学生参加，学生编号为 $1$ 到 $N$。每名学生为除自己外的另一名学生制作饼干或蛋糕中的一种。编号为 $i$ 的学生向编号为 $A_i$ 的学生赠送 $B_i$ 个自制的点心。 不同学生对收到的点心种类有不同偏好：有的希望收到与自己制作的种类相同的点心以进行口味研究，有的则希望收到不同种类的点心（若自制饼干则希望收到蛋糕，自制蛋糕则希望收到饼干）以增添乐趣。编号为 $i$ 的学生每收到一个与自己制作种类相同的点心，其 **喜悦值** 增加 $C_i$ 点；每收到一个不同种类的点心，其 **喜悦值** 增加 $D_i$ 点。当 $N$ 名学生合理选择制作饼干或蛋糕时，他们的 **喜悦值** 总和最大可达多少？ ### 任务 给定学生赠送点心的对象、数量及喜悦值信息，编写程序计算 **喜悦值** 总和的最大值。

从标准输入读取以下输入数据： - 第 $1$ 行包含整数 $N$，表示 JOI 学园的学生人数。 - 后续 $N$ 行中，第 $i$ 行（$1 \leq i \leq N$）包含以空格分隔的整数 $A_i, B_i, C_i, D_i$，表示编号 $i$ 的学生向编号 $A_i$（$1 \leq A_i \leq N$，$A_i \neq i$）的学生赠送 $B_i$ 个点心，且每收到一个同种类点心获得 $C_i$ 点喜悦值，每收到一个不同种类点心获得 $D_i$ 点喜悦值。

向标准输出输出一行，表示 $N$ 名学生 **喜悦值** 总和的最大值。

### 样例 1 解释 在此示例中，例如，当编号 $1, 2, 5, 6$ 的学生制作饼干，编号 $3, 4, 7$ 的学生制作蛋糕时： - 编号 $1$ 的学生收到 $8$ 个饼干和 $8$ 个蛋糕，**喜悦值** 为 $88$， - 编号 $2$ 的学生收到 $5$ 个蛋糕，**喜悦值** 为 $40$， - 编号 $3$ 的学生收到 $10$ 个饼干，**喜悦值** 为 $90$， - 编号 $4$ 的学生收到 $5$ 个蛋糕，**喜悦值** 为 $35$， - 编号 $5$ 的学生未收到任何点心，**喜悦值** 为 $0$， - 编号 $6$ 的学生未收到任何点心，**喜悦值** 为 $0$， - 编号 $7$ 的学生收到 $2$ 个饼干，**喜悦值** 为 $4$， 此时 **喜悦值** 总和为 $257$。 ### 限制 所有输入数据满足以下条件： - $2 \leq N \leq 100\,000$ - $1 \leq B_i \leq 1\,000\,000$ ($1 \leq i \leq N$) - $1 \leq C_i \leq 1\,000\,000$ ($1 \leq i \leq N$) - $1 \leq D_i \leq 1\,000\,000$ ($1 \leq i \leq N$) ### 子任务 #### 子任务 1 [10 分] - 满足 $N \leq 16$ #### 子任务 2 [20 分] - 满足 $N \leq 5\,000$ #### 子任务 3 [70 分] - 无额外限制 翻译由 DeepSeek V3 完成