지역 순회

경기과학고등학교 출신 정치인들은 서로의 성공을 돕기 위해 모여 정당 경곽당을 창당했다. 이번 대선에 후보로 등록한 정후도 경곽당 소속이며, 전국을 돌면서 공약을 홍보할 예정이다.

전국에는 1부터 $N$까지 번호가 하나씩 매겨진 $N$개의 지역이 있고, 지역 사이를 잇는 $N - 1$개의 길이 있다. 어느 두 지역이든 길을 따라 오갈 수 있다.

각 지역에는 경곽 로컬 당지부, 즉 경로당이 하나씩 있다. 정후는 경로당 하나에서 출발해 출발한 곳과 다른 경로당에서 끝나도록 지역을 순회한다. 같은 길은 최대 한 번만 지난다.

순회하는 과정에서 지나는 지역 중 일부를 골라 공약을 홍보한다. $i$번 지역에서 홍보하면 정치적 지지 $a_i$를 얻고 시간 $t_i$가 걸린다. $a_i$는 0 이하일 수도 있다. 다만 지역 균형 발전을 위해, 순회하는 순서에서 연속한 $M$개의 지역 가운데 적어도 한 곳에서는 반드시 홍보해야 한다. 순회에 걸리는 총 시간은 홍보에 쓴 시간의 합이다. 출발한 곳과 끝낸 곳에서는 반드시 홍보해야 한다.

정후의 측근 영우와 종경이는 순회 경로를 두고 의견이 갈린다. 영우는 정치적 지지의 합이 최대가 되도록 순회해야 한다고 주장하고, 종경이는 정치적 지지의 합을 걸리는 총 시간으로 나눈 값이 최대가 되도록 순회해야 한다고 주장한다. 두 기준의 최댓값을 각각 구하라. 두 경우의 경로는 서로 달라도 된다.

첫째 줄에 두 정수 $N$, $M$이 공백으로 구분되어 주어진다. 둘째 줄부터 $N - 1$개의 줄에 걸쳐 두 정수 $u_i$, $v_i$가 공백으로 구분되어 주어진다. 이는 지역 $u_i$와 지역 $v_i$가 길로 연결되어 있다는 뜻이다. $N + 1$번째 줄부터 $N$개의 줄에 걸쳐 $i$번째 줄에 두 정수 $a_i$, $t_i$가 공백으로 구분되어 주어진다.

한 줄에 공백으로 구분된 두 실수를 출력한다. 첫 번째 실수는 정치적 지지 합의 최댓값이고, 두 번째 실수는 정치적 지지 합을 총 시간으로 나눈 값의 최댓값이다. 절대 오차 또는 상대 오차가 $10^{-6}$ 이하이면 정답으로 인정한다. 첫 번째 실수만 맞히거나 두 번째 실수만 맞히면 점수의 절반을 받는다. 두 실수를 모두 맞혀야 점수를 전부 받는다.

• $2 \leq N \leq 100{,}000$
• $1 \leq M \leq N$
• $1 \leq u_i < v_i \leq N$
• $1 \leq t_i \leq 10^{9}$
• $-10^{9} \leq a_i \leq 10^{9}$
• 주어지는 모든 수는 정수이다.