Giải bài trực tuyến

Quái vật sau khi để hoàng tử chạy thoát khỏi mê cung của mình bây giờ đã trở nên thông minh hơn. Nó mang công chúa đến giam giữ trong lãnh địa của mình. Lãnh địa của quái vật có N ngôi làng bỏ hoang và các con đường mòn nối giữa các ngôi làng với nhau đi xuyên qua những cánh rừng sâu thăm thẳm. Vì quái vật rất thông minh, nó chỉ giữ lại những con đường cần thiết để có thể đi lại giữa hai ngôi làng bất kì trong lãnh địa của mình và dùng ma thuật của mình để xóa đi dấu vết của các con đường khác.

Hoàng tử biết rất rõ về lãnh địa của quái vật cũng như biết rằng quái vật có thể giam giữ công chúa ở trong một ngôi làng nào đó hoặc một nơi bất kì trong các cánh rừng bao quanh những con đường mòn. Ban đầu, hoàng tử sẽ cho quân lính lập doanh trại tại các ngôi làng ở biên giới của lãnh địa. Đặc điểm của những ngôi làng này là chỉ có tối đa một con đường mòn dẫn tới nó. Sau đó, hoàng tử sẽ điều động quân lính của mình đi theo các con đường mòn để tìm ra nơi công chúa bị giam giữ. Quá trình tìm kiếm được mô tả như sau:

• Do quái vật rất cảnh giác, mỗi ngày chỉ có một nhóm quân lính được điều động đi tìm kiếm để tránh bị quái vật phát hiện và thay đổi nơi giam giữ công chúa.
• Nhóm quân lính tìm kiếm phải được điều động từ một doanh trại, đi qua các con đường và các ngôi làng rồi dừng chân tại doanh trại đầu tiên họ gặp.
• Nếu trên đường đi, nhóm quân lính đi qua một ngôi làng bỏ hoang, thì sau khi nhóm quân lính rời ngôi làng, một phần trong số họ sẽ ở lại và đặt một doanh trại mới tại ngôi làng này. Số quân lính của hoàng tử là rất lớn nên đảm bảo luôn có đủ người để lập doanh trại mới. Lưu ý, điều này có nghĩa là tại thời điểm nhóm quân lính xuất phát, đích đến cuối cùng của họ phải có sẵn một doanh trại từ trước.
• Tất cả các ngôi làng đều có doanh trại và mỗi con đường trong lãnh địa phải được đi qua đúng một lần.

Độ dài của một hành trình tìm kiếm là số con đường nhóm quân lính phải đi qua. Một hành trình có độ dài i sẽ có chi phí là C_i. Do muốn nhóm quân lính có nhiều thời gian tìm kiếm hơn trên mỗi con đường đi qua, hoàng tử muốn lên kế hoạch sao cho độ dài của hành trình dài nhất là nhỏ nhất có thể. Trong những cách thỏa mãn điều kiện trên, hoàng tử muốn chọn cách có tổng chi phí là nhỏ nhất.

Input

• Dòng 1 chứa số N
• N - 1 dòng tiếp theo, mỗi dòng chứa 2 số x và y mô tả con đường nối giữa ngôi làng thứ x và ngôi làng thứ y
• Dòng cuối chứa N - 1 số C_i là chi phí của hành trình với độ dài tương ứng.

Output

• 2 số nguyên S và T, S là độ dài nhỏ nhất có thể của hành trình dài nhất và T là tổng chi phí nhỏ nhất trong các hành trình thỏa mãn giá trị S tìm được.

Giới hạn

• 1 ≤ N ≤ 4000
• Trong 40% số test N ≤ 30
• 1 ≤ x, y ≤ N
• 1 ≤ C_i ≤ 10⁶

Example

Input:

5

2 5

1 3

2 1

4 2

1 10 15 19

Output:

2 20

Giải thích

Các hành trình là:

• Ngày 1: 5-2-4 (chi phí: 10)
• Ngày 2: 3-1-2 (chi phí: 10)

Nếu đi hành trình 3-1-2 vào ngày 1 thì không hợp lệ vì ngôi làng thứ 2 vào lúc đó chưa có doanh trại.

Một cách đi khác là:

• Ngày 1: 5-2-1-3 (chi phí: 15)
• Ngày 2: 2-4 (chi phí: 1)

Chi phí cách đi này là 16, nhỏ hơn cách bên trên tuy nhiên độ dài hành trình dài nhất là 3, không tối ưu.