Cắt bảng

View as PDF

Submit solution


Points: 1.67 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
POI 2005
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

SNAD muốn cắt một bảng hình chữ nhật kích thước ~M \times N~ thành các hình chữ nhật con chiều dài hoặc chiều rộng là ~1~. Mỗi lần cắt như vậy SNAD chỉ có thể cắt trên rìa của bảng hình chữ nhật đó, có nghĩa là có thể chọn ~1~ trong ~4~ phương án: cắt dòng đầu tiên, cắt dòng cuối cùng, cắt cột đầu tiên, cắt cột cuối cùng. Tuy nhiên tổng các số trong hình chữ nhật con như vậy không được vướt quá ~P~. Bạn hãy giúp SNAD tìm cách cắt bảng ban đầu thành ít hình chữ nhật con nhất có thể

Input

Dòng đầu gồm ~3~ số ~P, N, M~ ~(P < 200000000, 0 < M, N < 2001)~

~M~ dòng sau mô tả ma trận hình chữ nhật kích thước ~M \times N~, các số trên ma trận nhỏ hơn ~100000~

Output

Ghi số duy nhất là kết quả nhỏ nhất có thể

Sample Input

12 6 4
6 0 4 8 0 5
0 4 5 4 6 0
0 5 6 5 6 0
5 4 0 0 5 4

Sample Output

8

Comments

Please read the guidelines before commenting.


There are no comments at the moment.