Gia đình

Một gia phả gồm nhiều thế hệ, mỗi thế hệ có thể có nhiều gia đình. Một gia đình gồm một người chồng và một người vợ, mỗi người đều có tài sản riêng hoặc nợ riêng.

Trong gia đình có thể có những người đã mất; khi đó, tài sản và nợ của người đó sẽ được phân chia như sau:

• Nếu trong gia đình chỉ có một người mất, tài sản và nợ của người đó sẽ được chia đều cho người còn lại và các con.
• Nếu cả hai vợ chồng đều đã mất:
  • Nếu họ có con, tài sản và nợ sẽ được chia đều cho các con.
  • Nếu cả hai vợ chồng ở một gia đình con đều đã mất, phần tài sản thừa kế trước đó sẽ tiếp tục được chia đều cho các con của gia đình con đó (nếu có).
  • Nếu không có con cái để thừa kế hoặc gánh nợ, khoản tiền thừa kế và nợ đó sẽ được xóa bỏ.
  • Gia đình có cả hai vợ chồng đều đã mất có tổng tài sản bằng $0$.
• Luôn đảm bảo trong gia phả có ít nhất một gia đình có người còn sống.

Biết rằng gia phả trong bài toán này có cấu trúc dạng cây và mỗi gia đình đều có đầy đủ cả vợ lẫn chồng. Hãy tìm tài sản của gia đình có tài sản lớn thứ $K$ trong gia phả.

Đầu vào: Thông tin của mỗi gia đình gồm 5 thành phần:

• Một số thực moneyHusband là tài sản hoặc nợ của người chồng.
• Một chuỗi ký tự thể hiện tình trạng của người chồng (Dead nếu đã mất, Alive nếu còn sống).
• Một số thực moneyWife là tài sản hoặc nợ của người vợ.
• Một chuỗi ký tự thể hiện tình trạng của người vợ (Dead nếu đã mất, Alive nếu còn sống).
• Một số nguyên không âm m là số người con của hai vợ chồng.

Cấu trúc dữ liệu đầu vào:

• Dòng 1: Chứa số nguyên dương $K$ ($K$ luôn nhỏ hơn hoặc bằng số lượng gia đình trong gia tộc).
• Dòng 2: Chứa thông tin của gia đình tộc trưởng (tổ tiên của tất cả các gia đình còn lại).
• Các dòng tiếp theo: Mỗi dòng chứa thông tin của $1$ gia đình con của các gia đình đã được nhập trước đó (lần lượt theo thứ tự xuất hiện).

Đầu ra: In ra trên một dòng duy nhất tổng tài sản của gia đình có tài sản lớn thứ $K$. Kết quả được làm tròn đến 2 chữ số thập phân. Đáp án được chấp nhận nếu chênh lệch với kết quả đúng không quá $0.01$.

Ràng buộc: Gọi $n$ là số lượng gia đình trong gia tộc.

• $1 \leq K \leq n \leq 10^{4}$ và $m \leq 10^4$.
• $|moneyHusband|, |moneyWife| \leq 10^6$.

Subtask 1: Tất cả mọi người đều còn sống (40% số điểm).
Subtask 2: Các trường hợp còn lại (60% số điểm).

Giải thích: Tổng tài sản của các gia đình sau khi sắp xếp tăng dần lần lượt là: -1000, 0, 55, 95, 100, 200. Do đó, gia đình có tài sản lớn thứ $3$ là gia đình có tổng tài sản là 95.

Ví dụ 1:

Đầu vào:

3
100 Alive -100 Alive 2
80 Alive 120 Alive 2
90 Dead 10 Alive 1
50 Alive 50 Alive 0
-1000 Alive 0 Alive 0
0 Alive 50 Alive 0

Đầu ra:

95.00