DreamTeam Selection

William, like most respectable Italians, pursues his personal conflict of interest with supreme passion. He really loves being both an organizer of the Italian IOIT contests, and coaching his personal team for the same competition! His team (the RoseToPCoders) did not made it through this year’s competition, so it’s time to plan for a better performance next year.

William has already selected a shortlist consisting of $N$ students, numbered from $0$ to $N − 1$, each of them with a best friend $F_i$. Remember that best-friendship is always symmetrical: if $a$’s best friend is $b$, then $b$’s best friend is $a$. William knows his buddies very well: for each of them, he measured how many points $P_i$ the student is able to score in a typical competition if his best friend is not in the team, and how many points $Q_i \leq P_i$ the student is able to score if his best friend is in the team (the presence of a friend is always distracting).

Help William choose the best team consisting of exactly $K$ contestants for next year’s competition!

Input data

The first line contains two integers $N$, $K$. Each of the following $N$ lines contains $3$ integers $F_i$, $P_i$, $Q_i$.

Output data

You need to write a single line with an integer: the maximum number of points that a team of exactly $K$ contestants (among the $N$ given) can score in a typical competition, taking friendships into account.

Constraints and clarifications

• $1 \leq K \leq N \leq 100 \ 000$.
• $0 \leq F_i < N$ for each $i = 0 \dots N − 1$.
• $0 \leq Q_i \leq P_i \leq 20 \ 000$ for each $i = 0 \dots N − 1$.
• Best-friendship is symmetrical: $F_i = j$ if and only if $F_j = i$ for each $i, j = 0 \dots N − 1$.
• $N$ is even and no student is best friend of himself: $F_i \neq i$ for each $i = 0 \dots N − 1$.

Example 1

stdin

4 1
2 20 15
3 70 0
0 10 10
1 50 0

stdout

70

Explanation

In the first sample case, the single best student is number $1$.

Example 2

stdin

6 3
2 40 30
4 90 70
0 75 10
5 20 0
1 80 80
3 50 50

stdout

225

Explanation

In the second sample case, the best team consists of students $1$, $2$ and $4$ for a total of $70$ + $75$ + $80$ = $225$ points (since $1$ and $4$ are best friends). The best team avoiding friendships would instead be $1$, $2$ and $5$ scoring $90$ + $75$ + $50$ = $215$ points.