Gathering in the Capital

In a kingdom, there are (n) houses connected by (n-1) bidirectional roads forming a tree, with the capital located at house 1. There are (m) people residing in various houses, and each person has a fixed speed denoted by (s_i), which represents the maximum number of steps they can travel in one day. Each road takes 1 step to traverse. The task is to compute the minimum number of days required such that all people can gather at the capital. For each person starting at a house with distance (d_i) from the capital, the number of days needed is given by (days_i = \lceil \frac{d_i}{s_i} \rceil). The final answer is the maximum (days_i) among all people.

inputFormat

Input is provided from standard input in the following format:

• The first line contains two integers (n) and (m), representing the number of houses and the number of people respectively.
• The next (n-1) lines each contain two integers (u) and (v), representing a bidirectional road between houses (u) and (v).
• The following (m) lines each contain two integers: the first integer indicates the house where a person lives, and the second integer indicates the number of steps they can travel in one day.

outputFormat

Output a single integer: the minimum number of days required for all people to gather at the capital (house 1).## sample

6 4
1 2
1 3
2 4
2 5
3 6
4 2
5 1
6 1
1 1

2