Junoh is top talent!!

Time limit2sMemory limit512 MB

Summary

In a weighted tree, find a simple path with the maximum number of nodes, then among those pick the one with the smallest total edge weight, and report that weight divided by T rounded up.

Level: Medium7 of 10
Topics: Tree, DFS, Dynamic programming, Greedy
Solved: No attempts yet

Problem

Junoh got an assignment from his mentor. The problem solving system used in the assignment works like this.

There are $N$ problems and $N-1$ links, and each link joins two different problems. A link works in both directions.
Starting from any problem, you reach every other problem by following links.
For any two problems $A$ and $B$ , exactly one route leads from $A$ to $B$ .

Junoh picks any one of the $N$ problems and starts the test there. The first problem he picks counts as a bonus and is solved in 0 seconds. After solving a problem he chooses one of the links attached to it and moves to the problem on the other end. Passing a link costs the time written on that link, and the time to solve $B$ after $A$ equals the time to solve $A$ after $B$ . He can never go back to a problem he has already passed.

Junoh wants to solve as many problems as this system allows. He can spend $T$ time on solving problems each day, and when a day's time runs out he continues the rest on the next day. The work may be cut at a day boundary. So if the link times along the chosen route add up to $S$ , the number of days is $S$ divided by $T$ , rounded up. For example, with $T = 4$ and a route whose link times are 3, 3, 3, the sum is 9, so the work splits into 4 + 4 + 1 and takes three days.

If several routes pass the maximum number of problems, Junoh takes the one that needs the fewest days. Given $N$ , $T$ and the links, compute the number of days.

Input

The first line contains the number of problems $N$ and the daily solving time $T$ ( $2 \le N \le 50000$ , $1 \le T \le 100000$ ). Each of the next $N-1$ lines contains three integers $A$ , $B$ , $C$ ( $1 \le A, B \le N$ , $1 \le C \le 1000$ ). $A$ and $B$ are the numbers of the two problems joined by a link, and $C$ is the time it takes to solve $B$ after $A$ , or $A$ after $B$ .

Output

Print the smallest number of days Junoh needs to solve as many problems as possible.

Examples3

Example 1
Input
```
6 4
1 2 4
2 3 2
3 4 7
3 5 3
6 5 4
```
Expected output
```
4
```
Example 2
Input
```
2 1
1 2 1
```
Expected output
```
1
```
Example 3
Input
```
4 4
1 2 3
2 3 3
3 4 3
```
Expected output
```
3
```