Giám đốc một công ty trách nhiệm hữu hạn muốn xin chữ ký của ông Kiến trúc sư trưởng thành phố phê duyệt dự án xây dựng trụ sở làm việc của công ty. Ông kiến trúc sư trưởng chỉ ký vào giấy phép khi bà thư ký của ông ta đã ký duyệt vào giấy phép. Bà thư ký làm việc tại tầng thứ M của toà nhà trụ sở làm việc gồm M | 012. XIN CHỮ KÝ Giám đốc một công ty trách nhiệm hữu hạn muốn xin chữ ký của ông Kiến trúc sư trưởng thành phố phê duyệt dự án xây dựng trụ sở làm việc của công ty. Ông kiến trúc sư trưởng chỉ ký vào giấy phép khi bà thư ký của ông ta đã ký duyệt vào giấy phép. Bà thư ký làm việc tại tầng thứ M của toà nhà trụ sở làm việc gồm M tầng của Văn phòng Kiến trúc sư trưởng thành phố. Các tầng của toà nhà được đánh số từ 1 đến M từ thấp đến cao. Mỗi tầng của toà nhà có N phòng được đánh số từ 1 đến N từ trái qua phải. Trong mỗi phòng chỉ có một nhân viên làm việc. Giấy phép chỉ được bà thư ký ký duyệt khi đã có ít nhất một nhân viên ở tầng M đã ký xác nhận. Ngoài bà thư ký một nhân viên bất kỳ chỉ ký xác nhận vào giấy phép khi có ít nhất một trong các điều kiện sau được thoả mãn a Nhân viên đó làm việc ở tầng 1 b Giấy phép đã được ký xác nhận bởi nhân viên làm việc ở cùng số phòng trong tầng sát dưới c Giấy phép đã được ký xác nhận bởi nhân viên làm việc ở cùng số phòng trong tầng sát trên d Giấy phép đã được ký xác nhận bởi nhân viên làm việc ở phòng bên cạnh Mỗi một nhân viên kể cả bà thư ký khi ký xác nhận đều đòi một khoản lệ phí. Hãy chỉ ra cách xin được chữ ký của Kiến trúc sư trưởng đòi hỏi tổng lệ phí phải trả là nhỏ nhất giả thiết rằng riêng chữ ký của Kiến trúc sư trưởng không mất lệ phí . Dữ liệu vào từ file văn bản Dòng đầu tiên chứa ba số M N P 1 M 50 1 N 100 1 P N ở đây P là số phòng bà thư ký. Dòng thứ i trong số M dòng tiếp theo chứa N số nguyên dương theo thứ tự là lệ phí phải trả cho các nhân viên ở các phòng 1 2 . N trên tầng i. Các số này không vượt quá 109 và giả thiết rằng tổng chi phí cần trả cũng không vượt quá 109. Kết quả Ghi ra file văn bản Dòng đầu tiên ghi 2 số F K theo thứ tự là chi phí cần trả và số lượng phòng cần đi qua. K dòng tiếp theo mỗi dòng ghi số tầng và số phòng của một phòng theo thứ tự cần đi qua. Các số trên 1 dòng của input output file cách nhau ít nhất 1 dấu trống Ví dụ 3 4 4 10 10 1 10 2 2 2 10 1 10
