#1234. SIGN - 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ý đuyệt vào giấy phép. Bà thư ký làm việc tại tầng thứ của toà nhà trụ sở làm việc gồ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ừ đến từ thấp đến cao. Mỗi tầng của toà nhà có phòng được đánh số từ đến từ trái qua phải. Trong mỗi phòng chỉ có 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 đã ký xác nhận. 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 ;
• 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 ở 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 ở phòng liền kề (hai phòng gọi là liên kề nếu chúng ở cùng tầng và chỉ số phòng sai khác nhau ).

Mỗi một nhân viên khi ký xác nhận đều đòi một khoản lệ phí.

Yêu cầu: 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ả cho các nhân viên là nhỏ nhất.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số ;
• Dòng thứ trong số dòng tiếp theo chứa số nguyên đương là lệ phí cần trả nhân viên ở các phòng trên tầng . Giả thiết là và tổng chi phí cần trả cũng không vượt quá .

Dữ liệu ra:

• Ghi ra tổng chỉ phí cần trả nhỏ nhất tìm được.

Vị dụ:

Dữ liệu vào:

3 4
10 10 1 10
2 2 2 10
1 10 10 10

Dữ liệu ra:

8