Có ~n~ người dân ở trong một thành phố được biểu diễn dưới dạng cây gồm ~n~ đỉnh thể hiện nhà của mỗi người dân cùng ~n-1~ cạnh có trọng số. Khi thảm hoạ xảy ra, ~n~ người dân này cần sơ tán về ~k~ điểm sơ tán theo đường đi ngắn nhất. Do các con đường có sức chứa vô hạn, nên thời gian cho việc sơ tán là thời gian dài nhất mà một người dân đến được điểm sơ tán. Tuy nhiên mỗi điểm sơ tán lại chỉ có một sức chứa nhất định.

Yêu cầu: Tìm thời gian ngắn nhất cần để sơ tán hết ~n~ người dân.

Input

• Dòng đầu tiên chứa 2 số nguyên ~n,k~ (~n \le 10^5,k \le 20~)

• ~n-1~ dòng sau mỗi dòng chứa 3 số nguyên ~u,v,w~ thể hiện một cạnh của cây (~1 \le u, v \le n, 1 \le w \le 10^9~)

• ~k~ dòng sau mỗi dòng chứa 2 số nguyên ~u, v~ thể hiện một điểm sơ tán và sức chứa của nó (~1 \le u \le n, 1 \le v \le 10^9~). Input đảm bảo ~\Sigma v \ge n~

Output

• Một dòng duy nhất là thời gian ngắn nhất để sơ tán toàn bộ người dân

Sample Input 1

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

Sample Output 1

11