It's a well-known fact that MMM, the greatest general in history, loves traveling.
This time she is setting off to Tianjin, a city famous for stuffed-bun, with her MMM Army. Tianjin is a city with N sites. And N sites are divided into several areas. Each site belongs to exactly one area. For each area, the number of sites and the number of street connected them are equal, and each pair of sites belong to the same area, there existed at least one simple path going from one site to the other. For each pair of sites belong to different area, no streets will connect them. The deliciousness of buns in the bakehouse on the i-th site is evaluated as an integer Wi. As MMM wants to maintain Bureaucratic Government (BG for short) to her army, she would invite them to every bakehouse on their way. But there is one problem: MMM hates to visit a site twice because 2 is an ominous number to her. However, they could choose to take the subway if in need. The subway in Tianjin is well developed so they can transport from any sites to any other sites conveniently even if when they are not connected by the streets. But MMM will feel carsick if they take the subway K times or more.
Now the question is, what's the maximum total deliciousness can MMM reach without carsickness? Note that with the convenient subway the MMM Army can start and end their journey in any site.