题目描述

题目译自 JOISC 2013 Day4 T2 「プレゼント」

在 JOI 学园，每年白色情人节期间都会举办一场甜点礼物交换会。今年参加交换会的有 $N$ 名学生，分别编号为 $1$ 到 $N$。每位学生为其他某位学生准备了饼干或蛋糕作为礼物。编号为 $i$ 的学生会将自己制作的甜点送给编号为 $A_{i}$ 的学生，数量为 $B_{i}$ 个。

有些学生希望收到与自己制作的甜点相同种类的东西，以便研究味道；而有些学生则希望收到不同种类的甜点（制作饼干则希望收到蛋糕，制作蛋糕则希望收到饼干），以增加乐趣。编号为 $i$ 的学生每收到一个与自己制作的甜点相同种类的甜点，「开心度」增加 $C_{i}$ 点；每收到一个不同种类的甜点，「开心度」增加 $D_{i}$ 点。你需要合理选择 $N$ 名学生制作饼干或蛋糕，以使得所有学生的「开心度」总和最大化，最终能达到多少？

给定学生赠送礼物的对象、数量以及「开心度」信息，你需要编写一个程序，计算所有学生「开心度」总和的最大值。

输入格式

从标准输入中读取以下数据：

• 第一行包含一个整数 $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, 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 100000$
• $1 \leq B_{i} \leq 1000000$ $(1 \leq i \leq N)$
• $1 \leq C_{i} \leq 1000000$ $(1 \leq i \leq N)$
• $1 \leq D_{i} \leq 1000000$ $(1 \leq i \leq N)$

详细子任务附加限制及分值如下表所示。