{"raw_statement":[{"iden":"statement","content":"В галактике Печеньковая Система находится планета Чаёчек. Жители планеты очень любят печеньки, поэтому каждый имеет своё хранилище печенек. У нашего героя, Ивана Ксеноморфа, тоже есть склад с печеньками. Так как он любит порядок во всём, его склад представляет собой прямоугольное здание размером N на M метров, причём всё пространство склада занимают ящики с печеньками с площадью основания 1 м2 каждый. В каждом ящике лежит определённое количество печенек. \n\nЗавтра к Ивану Ксеноморфу нагрянут родственники. Дабы не сильно крушить свой склад, он решил выбрать прямоугольник, состоящий из K ящиков с печеньками, и угостить родственников печеньками только из этих ящиков. Но так как Иван Ксеноморф не хочет делиться с другими своей прелестью, он хочет минимизировать количество печенек, которым он угостит гостей. Помогите Ивану Ксеноморфу сохранить как можно больше печенек себе.\n\nВ первой строке даны натуральные числа N и M (1 ≤ N, М ≤ 103) – размер склада Ивана Ксеноморфа.\n\nДалее следуют N строк по М целых неотрицательных чисел в каждой. Где aij – количество печенек в j-ом ящике i-го ряда (0 ≤ aij ≤ 106). \n\nВ последней строке указанно единственное число K (1 ≤ K ≤ 103).\n\nВ единственной строке выведите число – минимальное количество печенек, которое придётся отдать гостям. Если ответа не существует, выведите «-1».\n\nВ первом примере минимальная сумма 11 = 4+5+1+1.\n\nВо втором примере минимальная сумма 4 = 1+1+1+1.\n\n"},{"iden":"входные данные","content":"В первой строке даны натуральные числа N и M (1 ≤ N, М ≤ 103) – размер склада Ивана Ксеноморфа.Далее следуют N строк по М целых неотрицательных чисел в каждой. Где aij – количество печенек в j-ом ящике i-го ряда (0 ≤ aij ≤ 106). В последней строке указанно единственное число K (1 ≤ K ≤ 103)."},{"iden":"выходные данные","content":"В единственной строке выведите число – минимальное количество печенек, которое придётся отдать гостям. Если ответа не существует, выведите «-1»."},{"iden":"примеры","content":"Входные данные3 31 2 34 5 61 1 24Выходные данные11Входные данные2 41 1 1 12 2 3 44Выходные данные4"},{"iden":"примечание","content":"В первом примере минимальная сумма 11 = 4+5+1+1.Во втором примере минимальная сумма 4 = 1+1+1+1."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N, M \\in \\mathbb{Z}^+ $ be the dimensions of the warehouse grid.  \nLet $ A = (a_{i,j}) \\in \\mathbb{Z}_{\\geq 0}^{N \\times M} $ be the matrix where $ a_{i,j} $ is the number of cookies in the box at row $ i $, column $ j $.  \nLet $ K \\in \\mathbb{Z}^+ $ be the number of boxes to select.\n\n**Constraints**  \n1. $ 1 \\leq N, M \\leq 10^3 $  \n2. $ 0 \\leq a_{i,j} \\leq 10^6 $ for all $ i \\in \\{1, \\dots, N\\}, j \\in \\{1, \\dots, M\\} $  \n3. $ 1 \\leq K \\leq 10^3 $  \n\n**Objective**  \nFind the minimum possible sum of cookies in any axis-aligned rectangular subgrid of area exactly $ K $, i.e., find:  \n$$\n\\min \\left\\{ \\sum_{i=r_1}^{r_2} \\sum_{j=c_1}^{c_2} a_{i,j} \\;\\middle|\\; (r_2 - r_1 + 1) \\cdot (c_2 - c_1 + 1) = K,\\; 1 \\leq r_1 \\leq r_2 \\leq N,\\; 1 \\leq c_1 \\leq c_2 \\leq M \\right\\}\n$$  \nIf no such rectangle exists, output $-1$.","simple_statement":"Given an N×M grid where each cell has some cookies, find the minimum sum of cookies in any rectangular subgrid containing exactly K cells. If no such rectangle exists, output -1.","has_page_source":false}