(ledgl)

Baggio là một nhân viên sửa chữa bảng đèn Led. Một bảng đèn Led là một lưới hình chữ nhật có kích thước \(n \times m\) (\(n\) dòng, \(m\) cột, các đèn Led được đặt tại các ô vuông đơn vị trong lưới) và các mạch nối nối các đèn Led kề nhau (theo chiều đứng hoặc ngang). Một bảng đèn Led được gọi là hoàn chỉnh (không hỏng) nếu với hai đèn Led bất kỳ trên bảng đèn Led được nối với nhau bởi dãy các mạch nối (mạch nối đứng, mạch nối ngang). Với một bảng đèn Led bị hỏng, cần bổ sung các mạch nối để đảm bảo bảng đèn Led trở thành hoàn chỉnh. Biết rằng mạch nối đứng có chi phí là 1, mạch nối ngang có chi phí là 2.

Em hãy lập trình giúp Baggio bổ sung các đoạn mạch nối vào một bảng đèn Led bị hỏng để bảng đèn Led trở thành hoàn chỉnh sao cho chi phí mạch nối là thấp nhất.

+ Dữ liệu vào:

- Dòng 1: Chứa 2 số nguyên \(n\) và \(m\) \((1 \leq n,m \leq 100)\) là kích thước của bảng đèn Led bị hỏng.

- \(n\) dòng tiếp theo, mỗi dòng chứa \(m\) số nguyên cho biết các mạch nối còn tốt trong lưới. Chẳng hạn nếu giá trị của ô \((i,j)\) trong lưới \(n \times m\) là:

• 0 có nghĩa là không có mạch nối giữa đèn \((i,j)\) với đèn \((i + 1,j)\) và đèn \((i,j)\) với đèn \((i,j + 1)\).

• 1 có mạch nối giữa đèn \((i,j)\) với đèn \((i + 1,j)\) (mạch nối đứng).

• 2 có mạch nối giữa đèn \((i,j)\) với đèn \((i,j + 1\)) (mạch nối ngang).

• 3 có nghĩa là có mạch nối giữa đèn \((i,j)\) với đèn \((i + 1,j)\) và đèn \((i,j)\) với đèn \((i,j + 1)\).

+ Dữ liệu ra:

- Dòng đầu tiên chứa hai số nguyên \(K\) và \(L\), trong đó \(K\) là số mạch nối cần bổ sung trong cách bổ sung với chi phí nhỏ nhất tìm được, \(L\) là chi phí tương ứng.

- \(K\) dòng tiếp theo mỗi dòng chứa 3 số nguyên \(i,j,d\) trong đó \((i,j)\) là tọa độ đèn Led cần thêm mạch nối; \(d\) chỉ nhận một trong hai giá trị là 1 hoặc 2, với \(d = 1\) cho biết phải lắp thêm mạch nối đứng giữa đèn \((i,j)\) với đèn \((i + 1,j)\), \(d = 2\) cho biết phải lắp thêm mạch nối ngang giữa đèn \((i,j)\) với đèn \((i,j + 1)\).

+ Ví dụ:

+ Ràng buộc:

- Có 50% số lượng Test thõa mãn điều kiện \((1 \leq n,m \leq 50)\)

- Có 50% số lượng Test thõa mãn điều kiện \((51 \leq n,m \leq 100)\)