At JOI Academy, an annual gift exchange of sweets is held around White Day. $N$ students, numbered from $1$ to $N$, participate in this year's gift exchange. Each student makes either a cookie or a cake for one other student. Student $i$ gives $B_i$ pieces of the sweet they made to student $A_i$.

Some students want to study the taste by receiving the same type of sweet they made, while others want to enjoy a different type of sweet (a cake if they made a cookie, or a cookie if they made a cake). For every piece of the same type of sweet they made that student $i$ receives, their "happiness" increases by $C_i$ points, and for every piece of a different type of sweet they receive, their "happiness" increases by $D_i$ points. If the $N$ students choose whether to make cookies or cakes optimally, what is the maximum possible total "happiness" of the $N$ students?

Input

Read the following from standard input:

• The first line contains an integer $N$, representing the number of students at JOI Academy.
• The following $N$ lines, the $i$-th line ($1 \le i \le N$), contains integers $A_i, B_i, C_i, D_i$ separated by spaces, indicating that student $i$ gives $B_i$ pieces of sweets to student $A_i$ ($1 \le A_i \le N, A_i \neq i$), and that student $i$ gains $C_i$ points of "happiness" for each piece of the same type of sweet they receive, and $D_i$ points of "happiness" for each piece of a different type of sweet they receive.

Output

Output the maximum total "happiness" of the $N$ students in a single line.

Constraints

All input data satisfies the following conditions:

• $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$)

Subtasks

Subtask 1 [10 points]

• $N \le 16$ is satisfied.

Subtask 2 [20 points]

• $N \le 5\,000$ is satisfied.

Subtask 3 [70 points]

• No additional constraints.

Examples

Input 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

Output 1

257

Note

In this example, for instance, if students $1, 2, 5, 6$ make cookies and students $3, 4, 7$ make cakes:

• Student $1$ receives $8$ cookies and $8$ cakes, so their "happiness" is $88$.
• Student $2$ receives $5$ cakes, so their "happiness" is $40$.
• Student $3$ receives $10$ cookies, so their "happiness" is $90$.
• Student $4$ receives $5$ cakes, so their "happiness" is $35$.
• Student $5$ receives no sweets, so their "happiness" is $0$.
• Student $6$ receives no sweets, so their "happiness" is $0$.
• Student $7$ receives $2$ cookies, so their "happiness" is $4$.

The total "happiness" is $257$.