logo AlgoBeat OnlineJudge
登录 注册

#103144. [BZOJ 3144] [Hnoi2013]切糕

内存限制:128 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

经过千辛万苦小 A 得到了一块切糕,切糕的形状是长方体,小 A 打算拦腰将切糕切成两半分给小 B。出于美观考虑,小 A 希望切面能尽量光滑且和谐。于是她找到你,希望你能帮她找出最好的切割方案。出于简便考虑,我们将切糕视作一个长 、宽 、高 的长方体点阵。我们将位于第 层中第 行、第 列上的点称 ,它有一个非负的不和谐值 。一个合法的切面满足以下两个条件:

  • 与每个纵轴(一共有 个纵轴)有且仅有一个交点。即切面是一个函数 ,对于所有 ,我们需指定一个切割点 ,且
  • 切面需要满足一定的光滑性要求,即相邻纵轴上的切割点不能相距太远。

对于所有的 ,若 ,则 ,其中 是给定的一个非负整数。 可能有许多切面 满足上面的条件,小 A 希望找出总的切割点上的不和谐值最小的那个。

输入格式

第一行是三个正整数 ,表示切糕的长宽高。第二行有一个非负整数 ,表示光滑性要求。接下来是 列的矩阵,第 个矩阵的第 行第 列是

输出格式

仅包含一个整数,表示在合法基础上最小的总不和谐值。

样例

样例输入 #1

2 2 2
1
6 1
6 1
2 6
2 6

样例输出 #1

6

样例说明

最佳切面的

数据范围与提示

对于 的数据,,且给出的所有的不和谐值不超过