Bờm được tặng một miếng Chocolate cực lớn hình chữ nhật kích thước  \(m \times n\)  được chia thành lưới ô vuông đơn vị ( \(m\ \)hàng và \(n\) cột). Bờm muốn cắt miếng chocolate ra làm nhiều mảnh để chia cho các bạn. Biết rằng Bờm được sử dụng không quá \(k\) nhát cắt thuộc 1 trong 2 loại sau:

+ Cắt ngang miếng chocolate từ trái qua phải theo rãnh giữa hai hàng ô liên tiếp.

+ Cắt dọc miếng chocolate từ trên xuống dưới theo rãnh giữa hai cột ô liên tiếp.

Yêu cầu: Giúp Bờm tìm cách cắt để chia miếng chocolate ra làm nhiều phần nhất.

Dữ liệu vào: 3 số nguyên dương \(m,\ n,\ k\)  cách nhau bởi dấu cách.

Giới hạn: \(m,\ n,\ k \geq 10^{9}\)

Kết quả: số phần chocolate rời nhau sau khi cắt theo phương án tìm được.

Ví dụ: