Hydra is some very greedy animal. A hydra has 9 heads when he is born, and many more new heads will come out when he grows up. Of course, some old heads will break off because of caducity.

One day, a hydra with M heads finds a tree with N fruits on it. He is very delighted and wants to eat this tree instantly. Since he has M heads, he must divide these N fruit into M groups, each group contains at least 1 fruit, and each head will eat a group of fruits.

The biggest head among the M heads is named "Boss", it must eat neither more nor less than K fruits, and, in the nature of things, the biggest fruit included. These fruits are connected by N-1 branches, and there exists a path made up with branches between each pair of fruit.

If two fruit connected by a single branch is put in different groups, the corresponding two heads will break the branch and eat the two fruits, otherwise the corresponding head will eat the two fruits without breaking the branch. Eating branches is not very comfortable of course, so every branch has a weight of illness, and the weight of illness of this hydra is the sum of the weights of illness of all branches he has eaten.

Your task is to help the hydra to minimize his weight of illness.

The picture below is an example.

N=8, M=2, K=4.The bigger head eats 4 fruits(full points), the smaller head eats 4 fruits(empty points). The branch signed by a thin segment is eaten by the hydra.

Input

Ten test cases(Given one after another, you have to process all!). For each test case the first line contains 3 integers N (1<=N<=300), M (2<=M<=N), K (1<=K<=N), separated by single spaces. The N fruits are numbered 1..N, and the biggest fruit is always numbered 1. N-1 lines follow, each contains 3 integers i, j, k separated by spaces denoted that there is a branch between fruit i (1<=i<=N) and fruit j (1<=j<=N) and the weight of illness of this branch is k(0<=k<=100000).

Output

Ten lines, each contains a single integer - the minimum weight of illness of the hydra. If we can't divide the fruit into M groups, output "-1"(without quotes).

Example

Input:
8 2 4
1 2 20
1 3 4 
1 4 13
2 5 10
2 6 12
3 7 15
3 8 5
[and 9 test cases more]

Output:
4
[and 9 test cases more]

Link

After solving this problem you can try the problem DRAGON2.