JOI 学园每年都会在白色情人节期间举办点心交换会。今年的交换会有 $N$ 名学生参加，学号分别为 1 到 $N$。每名学生都要为除自己以外的某一名学生制作饼干或蛋糕。学号为 $i$ 的学生会向学号为 $A_i$ 的学生赠送 $B_i$ 个他制作的点心。

有些学生希望收到与自己制作的点心种类相同的点心，以便研究口味；而另一些学生则希望收到与自己制作的点心种类不同的点心（如果自己做的是饼干就收蛋糕，如果做的是蛋糕就收饼干），以便享受乐趣。学号为 $i$ 的学生每收到 1 个与自己制作种类相同的点心，其“喜悦度”就会增加 $C_i$ 点；每收到 1 个与自己制作种类不同的点心，其“喜悦度”就会增加 $D_i$ 点。请问在 $N$ 名学生选择制作饼干还是蛋糕的最优策略下，所有学生“喜悦度”之和的最大值是多少？

题目描述

给定学生赠送点心的对象、数量以及“喜悦度”信息，编写一个程序，计算所有学生“喜悦度”之和的最大值。

输入格式

从标准输入读取以下内容：

• 第 1 行包含一个整数 $N$，表示 JOI 学园的学生人数。
• 接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）包含四个由空格分隔的整数 $A_i, B_i, C_i, D_i$，表示学号为 $i$ 的学生向学号为 $A_i$（$1 \le A_i \le N, A_i \neq i$）的学生赠送 $B_i$ 个点心，且该学生收到与自己制作种类相同的点心时获得 $C_i$ 点“喜悦度”，收到不同种类点心时获得 $D_i$ 点“喜悦度”。

输出格式

将 $N$ 名学生“喜悦度”之和的最大值输出到标准输出，占 1 行。

数据范围

所有输入数据满足以下条件：

• $2 \le N \le 100\,000$
• $1 \le B_i \le 1\,000\,000$ ($1 \le i \le N$)
• $1 \le C_i \le 1\,000\,000$ ($1 \le i \le N$)
• $1 \le D_i \le 1\,000\,000$ ($1 \le i \le N$)

子任务

子任务 1 [10 分] * 满足 $N \le 16$。

子任务 2 [20 分] * 满足 $N \le 5\,000$。

子任务 3 [70 分] * 无附加限制。

样例

样例输入 1

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

样例输出 1

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。