In this era of modern technology social media is the most powerful weapon and the viral issue is the most dangerous thing. You want to viral a meme about your friend. And you know about a social media named ‘Mukhchobi’. Now you want to viral the above-mentioned shitty things in ‘Mukhchobi’. In ‘Mukhchobi’ there are N users numbered from 1 to N. They all belong to some discrete community.
Now, what is a community? Well suppose A is connected with B and B is connected with C then A, B, C are in the same community.
And what is viral? Viral means at least K users of ‘Mukhchobi’ can get the meme.
If anyone from any community shares something in ‘Mukhchobi’ then all other members of that particular community can get shared things. Mind it you can’t share anything in ‘Mukhchobi’ as you’re not a user of it. To share something you need help from users of ‘Mukhchobi’ they will share in favor of you, but they demand charge. You need to pay A units of money if you want to make share by user numbered A. And you don’t want to waste many units of money to do this.
How can you viral the memes (Such that at least K user of ‘Mukhchobi’ can get the meme) with minimum cost? Can you? Okay, find the minimum cost.
Input starts with N, M and K. In the next M lines, you will be given U and V that means U is connected with V. It is guaranteed that you will not get any relation more than once.
Constraints:
1 <= K <= N <= 10000
0 <= M <= min(N * (N - 1) / 2, 1000000)
1 <= u, v <= N
Print a single integer mentioned above.
| Input | Output |
|---|---|
4 3 4 1 2 2 3 3 4 | 1 |