Trong \(D\) ngày liên tiếp, người bạn đời của bạn mua một loại hàng mỗi ngày trên chợ trực tuyến Nile.com. Chợ có \(N\) cửa hàng được đánh số từ \(1\) đến \(N\); mỗi ngày chọn đúng một cửa hàng để mua. Giá mỗi cửa hàng có thể thay đổi theo ngày và đã được thông báo trước.

Nếu mua tại cùng một cửa hàng trong hai ngày liên tiếp, giá ngày thứ hai được giảm \(10\%\). Nếu mua tại cùng cửa hàng từ ba ngày liên tiếp trở lên, giá ngày thứ ba và các ngày tiếp theo được giảm \(30\%\). Khi đổi cửa hàng, chuỗi ngày liên tiếp bắt đầu lại. Mọi giá niêm yết đều là bội của \(10\).

Hãy lập kế hoạch sao cho tổng tiền trả trong \(D\) ngày nhỏ nhất và tính tổng tiền đó.

Dữ liệu vào

Đọc từ đầu vào chuẩn gồm \(D+1\) dòng.

Dòng đầu chứa \(N,D\), với \(2 \le N \le 3000\), \(2 \le D \le 365\).

\(D\) dòng tiếp theo lần lượt ứng với các ngày. Mỗi dòng chứa \(N\) giá trước giảm, theo thứ tự cửa hàng. Mỗi giá là bội của \(10\) trong đoạn từ \(10\) đến \(100000\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa tổng tiền nhỏ nhất.

Chấm điểm

Giới hạn thời gian: \(1\) giây mỗi bộ dữ liệu. Giới hạn bộ nhớ: \(64\) MB.

Có \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm; tổng cộng \(100\) điểm. \(40\%\) số điểm ứng với \(N \le 200\); \(20\%\) toàn bộ dữ liệu có \(N \le 10\), \(D \le 10\). Các bảo đảm này không được hiểu là các nhóm rời nhau.

Ví dụ

4 5
50 30 80 70
50 30 50 40
50 50 60 50
30 90 40 50
70 30 70 80

152

4 5
110 160 80 200
150 170 80 120
80 150 160 160
160 110 200 110
150 190 160 190

481