402437: GYM100771 J Ксеноморфы любят печеньки

J. Ксеноморфы любят печенькиограничение по времени на тест1 секундаограничение по памяти на тест64 мегабайтавводстандартный вводвыводстандартный вывод

В галактике Печеньковая Система находится планета Чаёчек. Жители планеты очень любят печеньки, поэтому каждый имеет своё хранилище печенек. У нашего героя, Ивана Ксеноморфа, тоже есть склад с печеньками. Так как он любит порядок во всём, его склад представляет собой прямоугольное здание размером N на M метров, причём всё пространство склада занимают ящики с печеньками с площадью основания 1 м2 каждый. В каждом ящике лежит определённое количество печенек.

Завтра к Ивану Ксеноморфу нагрянут родственники. Дабы не сильно крушить свой склад, он решил выбрать прямоугольник, состоящий из K ящиков с печеньками, и угостить родственников печеньками только из этих ящиков. Но так как Иван Ксеноморф не хочет делиться с другими своей прелестью, он хочет минимизировать количество печенек, которым он угостит гостей. Помогите Ивану Ксеноморфу сохранить как можно больше печенек себе.

Входные данные

В первой строке даны натуральные числа N и M (1 ≤ N, М ≤ 10³) – размер склада Ивана Ксеноморфа.

Далее следуют N строк по М целых неотрицательных чисел в каждой. Где a_ij – количество печенек в j-ом ящике i-го ряда (0 ≤ a_ij ≤ 10⁶).

В последней строке указанно единственное число K (1 ≤ K ≤ 10³).

Выходные данные

В единственной строке выведите число – минимальное количество печенек, которое придётся отдать гостям. Если ответа не существует, выведите «-1».

ПримерыВходные данные

3 3
1 2 3
4 5 6
1 1 2
4

Выходные данные

11

Входные данные

2 4
1 1 1 1
2 2 3 4
4

Выходные данные

4

Примечание

В первом примере минимальная сумма 11 = 4+5+1+1.

Во втором примере минимальная сумма 4 = 1+1+1+1.