The legendary Nine-Headed Dragon is a particularly gluttonous creature. Although it is called a "Nine-Headed Dragon," this only refers to the fact that it had nine heads when it was born. During its growth, it sometimes grows many new heads, so the total number of heads is often much greater than nine; of course, some old heads may also fall off due to aging.

One day, a Nine-Headed Dragon with $M$ heads sees a fruit tree with $N$ fruits and is overjoyed, wishing to devour it all in one bite. However, it must take care of every head, so it needs to divide the $N$ fruits into $M$ groups, with at least one fruit in each group, so that each head eats one group.

Among these $M$ heads, there is one largest head, called the "Big Head," which is the leader of all heads. It must eat exactly $K$ fruits, and these $K$ fruits must naturally include the single largest fruit. The fruits are connected by $N-1$ branches. Since the fruit tree is a single entity, one can "walk" from any fruit to any other fruit along the branches.

For each branch, if the two fruits it connects need to be eaten by different heads, the two heads will work together to break the branch and separate the fruits; if the two fruits are eaten by the same head, that head will be too lazy to break it and will eat the fruits along with the branch. Of course, eating branches is not very comfortable, so each branch has a "discomfort value," and the Nine-Headed Dragon's total discomfort value is the sum of the "discomfort values" of all the branches eaten by the heads.

The Nine-Headed Dragon wants its "discomfort value" to be as small as possible. Can you help it calculate this?

For example, in the case shown in Figure 1, the fruit tree contains 8 fruits and 7 branches, and the "discomfort value" of each branch is marked next to it. The Nine-Headed Dragon has two heads, and the Big Head needs to eat 4 fruits, which must include the largest fruit. That is, $N=8$, $M=2$, $K=4$:

Figure 1 describes the shape of the fruit tree, and Figure 2 describes the optimal strategy. The Big Head eats 4 fruits, marked with solid dots; the small head eats 4 fruits, marked with hollow dots; the Nine-Headed Dragon's discomfort value is 4, because the branches marked with thin edges in the figure were eaten by the Big Head.

Input

The first line contains three integers $N$ ($1 \le N \le 300$), $M$ ($2 \le M \le N$), and $K$ ($1 \le K \le N$). The $N$ fruits are numbered $1, 2, \dots, N$, and the largest fruit is always numbered $1$. The next $N-1$ lines describe the shape of the fruit tree, each containing three integers $a$ ($1 \le a \le N$), $b$ ($1 \le b \le N$), and $c$ ($0 \le c \le 10^5$), indicating that there is a branch with a discomfort value of $c$ connecting fruit $a$ and fruit $b$.

Output

Output a single integer representing the minimum discomfort value of the Nine-Headed Dragon while satisfying the requirements of the "Big Head." If it is impossible to satisfy the requirements, output -1.

Examples

Input 1

8 2 4 
1 2 20 
1 3 4 
1 4 13 
2 5 10 
2 6 12 
3 7 15 
3 8 5

Output 1

4

Note

This example corresponds to the case described in the problem statement.