Thành phố Free Contest hiện đang có X +Y +Z mảnh đất trống, được đánh số từ 1 đến X +Y +Z.Anh Kiên - một tỉ phú của thành phố Free Contest, chủ tịch tập đoàn KC97 - đã quyết định mua lại X + Y + Z mảnh đất này. Với mảnh đất thứ i, anh có thể xây dựng một trong ba công trình sau:
• Trung tâm thương mại với lợi nhuận Ai
• Khu vui chơi với lợi nhuận Bi
• Nhà hàng với lợi nhuận Ci
Qua nghiên cứu thị trường, anh Kiên cho rằng nên xây dựng X trung tâm mua sắm, Y khu vui chơi và Z nhà hàng. Hãy tính tổng lợi nhuận tối đa mà anh Kiên có thể thu được nếu xây dựng các công trình trên một cách tối ưu.
Input
• Dòng đầu tiên chứa ba số nguyên dương X, Y , Z (X + Y + Z ≤ ~ 10^5 ~) - số trung tâm thương mại, khu vui chơi và nhà hàng cần xây dựng.
• X + Y + Z dòng tiếp theo, mỗi dòng gồm ba số nguyên Ai, Bi, Ci (0 ≤ Ai, Bi, Ci ≤ ~ 10^9 ~) lần lượt là lợi nhuận thu được khi xây dựng trung tâm thương mại, khu vui chơi và nhà hàng ở mảnh đất thứ i.
Output
• Gồm một số nguyên duy nhất là tổng lợi nhuận tối đa.
Sample
Input #1
3 2 1
0 3 2
1 4 9
5 3 2
7 5 9
4 8 9
3 0 4
Output #1
35
Hint
• Xây dựng trung tâm thương mại trên các mảnh đất 3, 4, 6; xây dựng khu vui chơi trên các mảnh đất 1, 5; xây dựng nhà hàng trên mảnh đất 2. Tổng lợi nhuận là: 3+9+5+7+8+3 = 35.
Problem source: Free Contest thi thử HSG QG V2
Bình luận