Ще більше веселощів
Так чудово спати під відкритим небом, просинатися під спів птахів і бачити первші промені сонця, що встає із-за горизонту...
Стоп, Ви ж не пам'ятаєте, як заснули посеред лісу. Єдине, що Ви пам'ятаєте, це те що Ви покривали щось трьома прямоуутниками. 0_о
Будучи невпевненим у тому, що ж це бцло, Ви придумали собі наступну задачу: Для заданої матриці, яка складається з цілих чисел, знайти k підматриць, які не перекриваються (іншими словами, прямокутних фрагментів), таких, щоб сума чисел у них була б найбільшою.
Вхідні дані
У першому рядку входу знаходяться три цілих числа n, m та k (1 ≤ k ≤ 3, k ≤ n, m ≤ 300), які задають кількість рядків, кількість стовбців, та число підматриць відповідно. Наступні n чисел описують матрицю по рядкам. Кожен з них містить послідовність m цілих чисел a_ij (-20000 ≤ a_ij ≤ 20000). Також відомо, що у 40% тестів 1 ≤ k ≤ 2.
Вихідні дані
Виведіть одне ціле число: найбільшу можливу суму чисел у k підматрицях заданої матриці. Підматриці можуть дотикатись, але вони не можуть мати спільних елементів.
