Giải bài trực tuyến

SNAD muốn cắt một bảng hình chữ nhật kích thước M x 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 x 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ể

Example

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
Output:
8