J. Divide the Villages
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have found $$$N$$$ villages that are all connected by $$$N - 1$$$ roads so that one can start at any village and visit any other village using these roads. However, the villagers in these villages don't want to be all connected because they think there are too many people competing over trading. So they ask for your help to break the villages up by removing roads.

Each road $$$i$$$ has a time $$$t_i$$$ that it takes to remove, but you only have $$$T$$$ time before your mom tells you to stop gaming. Therefore, the total time of the roads you remove must be at most $$$T$$$. Also, after removing roads, the villages are split into smaller communities where villages within a community can still visit each other using roads, but villages in different communities cannot visit each other anymore. To keep the villagers as happy as possible, you want to minimize the number of villages in the largest community. Help the villagers out as much as possible using your limited gaming time and find the minimum number of villages in the largest community!

Input

The first line of input contains two integers $$$N$$$ and $$$T$$$ ($$$2 \le N \le 1000$$$, $$$1\le T\le 10^9$$$): the number of villages and the amount of gaming time you have, respectively.

The $$$i$$$-th of the next $$$N - 1$$$ lines contains three integers $$$u, v, t_i$$$ ($$$1 \le u, v\le N$$$, $$$u\neq v$$$, $$$1\le t_i\leq 10^9$$$): road $$$i$$$ is between village $$$u$$$ and village $$$v$$$ and takes time $$$t_i$$$ to remove.

Output

Output a single integer: the minimum number of villages in the largest community after removing the optimal roads using your limited gaming time.

Examples
Input
5 6
1 2 2
2 3 4
3 4 2
4 5 2
Output
2
Input
5 6
1 2 7
2 3 7
3 4 7
4 5 7
Output
5
Note

For the first test case, you can remove roads $$$1$$$, $$$2$$$, and $$$4$$$, which takes a total time of $$$6$$$. Then, the communities would be villages $$$(1)$$$, $$$(2,3)$$$, $$$(4)$$$, and $$$(5)$$$. So, the largest community has $$$2$$$ villages, and we can show that no other removal of roads can result in a smaller size of the largest community.

For the second test case, it is impossible to remove any of the roads without going over your given gaming time. So, all the villages will remain connected and the largest community has size $$$5$$$.