题目描述

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$ 名学生 喜悦值 总和的最大值。

7
3 3 6 5
7 2 8 8
4 5 3 9
1 8 7 2
1 8 8 4
3 7 4 5
2 5 1 2

257

提示

样例 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 完成