DRAGON - Greedy Hydra

no tags 

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.


hide comments
aashishsharma: 2017-03-12 11:19:18

nice problem!

Hussain Kara Fallah: 2014-04-12 06:16:32

I think making M>2 is just for making the problem so complicated and longer in code ... just make m=2 and it will be nicer and as difficult as this :P


Added by:Fudan University Problem Setters
Date:2007-04-01
Time limit:9s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL GOSU JS-RHINO
Resource:Chinese National Olympiad in Informatics 2002,Day 1; translated by lcosvse