Mô tả và yêu cầu

Xếp đôminô
Cho một bảng có kích thước 𝑛 × 3 (𝑛 hàng và ba cột), các hàng được đánh số thứ tự từ 1
đến 𝑛, các cột được đánh số thứ tự từ 1 đến 3, ô nằm ở hàng thứ 𝑖 cột thứ 𝑗 là ô (𝑖, 𝑗). Trên
mỗi ô của bảng được ghi một số nguyên. Bạn có 𝑘 quân đôminô, mỗi quân đômino có kích
thước 2 × 1 (đặt vừa hai ô của bảng). Bạn muốn tìm cách đặt 𝑘 quân đôminô này lên bảng
sao cho mỗi quân nằm đúng trên hai ô, không có hai quân bất kỳ nào nằm chồng lên nhau
và tổng các số trên các mà các quân đôminô nằm là lớn nhất.
Yêu cầu: Hãy lập trình xác định giá trị lớn nhất tìm được.
Dữ liệu vào: cho trong file văn bản domino.inp có cấu trúc như sau:
 Dòng đầu ghi hai số nguyên dương 𝑛 và 𝑘 (𝑛, 𝑘 ≤ 1000).
 𝑛 dòng tiếp theo, mỗi dòng ghi ba số nguyên cho biết giá trị các số được ghi trên
bảng (mỗi số có trị tuyệt đối không vượt quá 106).
Kết quả: ghi ra file văn bản domino.out chỉ một số là kết quả tìm được.

Ví dụ

domino.inp                domino.out
                             2 2                       13
                             0 3 1
                             5 4 2