White Day Present Exchange

Every year around White Day, JOI Academy holds a cookie and cake exchange. This year's exchange has N students, numbered 1 through N. Each student makes either cookies or a cake for exactly one other student. Student i gives $B_i$ pieces of the treat they made to student $A_i$.

Some students want to receive the same kind of treat they made so they can study its taste, while others want to receive the other kind (cake if they made cookies, cookies if they made a cake) just for fun. Student i gains $C_i$ points of "happiness" for each piece of the same kind of treat they made that they receive, and $D_i$ points of "happiness" for each piece of the other kind they receive. If the N students choose well whether to make cookies or a cake, what is the largest possible total "happiness" of the N students?

Given each student's gift recipient and piece count, along with the "happiness" values, write a program to find the maximum total "happiness".

Read the following input from standard input.

• The first line contains the integer N, the number of students at JOI Academy.
• Of the following N lines, line i (1 ≤ i ≤ N) contains the integers $A_i$, $B_i$, $C_i$, $D_i$ separated by spaces. This means student i gives $B_i$ pieces of treat to student $A_i$ (1 ≤ $A_i$ ≤ N, $A_i$ ≠ i), gains $C_i$ points of "happiness" per piece of the same kind of treat they made that they receive, and gains $D_i$ points of "happiness" per piece of the other kind they receive.

Print the maximum total "happiness" of the N students on one line to standard output.

• 2 ≤ N ≤ 100 000.
• 1 ≤ $B_i$ ≤ 1 000 000 (1 ≤ i ≤ N).
• 1 ≤ $C_i$ ≤ 1 000 000 (1 ≤ i ≤ N).
• 1 ≤ $D_i$ ≤ 1 000 000 (1 ≤ i ≤ N).