Cây tăng trưởng (Growing Trees)

Nguồn: UVa

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có một cây $N$ đỉnh. Trọng số cạnh $(u,v)$ vào ngày $d$ là $c+a\cdot d$. Với một ngày $d$, độ dài đường đi là tổng trọng số cạnh trên đường đi và đường kính là giá trị lớn nhất giữa hai đỉnh. Hãy chọn ngày nguyên $0\le d\le K$ để đường kính nhỏ nhất.

Input

Dòng đầu chứa $N,K$. Mỗi trong $N-1$ dòng tiếp theo chứa $u,v,c,a$ của một cạnh.

Output

In ngày nhỏ nhất đạt đường kính tối thiểu, sau đó in giá trị đường kính tối thiểu.

Subtask

• Subtask 1 — 20 điểm: dữ liệu nhỏ, phù hợp để kiểm tra cách trực tiếp hoặc DP cơ bản.
• Subtask 2 — 30 điểm: dữ liệu trung bình, yêu cầu lưu trạng thái hợp lý.
• Subtask 3 — 50 điểm: toàn bộ giới hạn của gói Phước Hưng OJ.

Ví dụ

Input

3 5
1 2 10 -1
2 3 1 2

Output

0
11

Giải thích

Kết quả được tính đúng theo quy tắc của đề. Đây là một trường hợp nhỏ để đối chiếu định dạng vào/ra trước khi nộp bài.