P7640 [BalticOI 2006] CITY PLANNING (Day 2)

一个星球上将建造一个空间站。这个空间站将雇用 $N$ 人。他们必须住在某个地方，为此，空间站周围将建起一座城市。空间站周围的土地被划分为等大小的方形地块，每个地块上可以建一幢最高 $K$ 层的公寓楼。每幢楼每层都应有一套公寓，每个人都应住在单独的公寓里。其空间站的坐标为（$0$,$0$），其余的编号如下所示：  由于地块之间的交通只能在街道上通行，所以地块（$x$,$y$）到空间站的距离为 $|x|+|y|-1$ 个单位。 建造一幢座房子的费用等于建每层楼的费用之和。众所周知，建造一个楼层的成本取决于楼层的高度，而不是建筑的位置。 将要建造的房子将使用 $30$ 年。住在这些房子里的人将去空间站工作，在这 $30$ 年里，将他们运送到空间站和离开空间站将花费每人 $T·d$，其中 $d$ 是一个人的建筑到空间站的距离。 我们可以假设星球足够大，待建的城市只占地表的一小部分，所以我们不需要考虑星球表面的曲率。 你的任务是写一个程序来确定 $30$ 年来建造房屋和运营运输系统的最低总成本。

第一行包含整数 $N$，$T$和 $K$。接下来的 $K$ 行指定了每层楼的公寓建造成本。第 $i+1$ 行包含整数 $c_i$，表示在第 $i$ 层建造一套公寓的成本（假设所有第 $i−1$ 层以下都已经建造）。众所周知，建设一个较高的楼层总是比建设一个较低的楼层更昂贵：$c_1

唯一的一行包含一个整数——建设城市和运营交通系统 $30$ 年的总成本。

#### 数据规模与约定 对于 $100 \%$ 的数据，$1 \le N \le 10^{12}$，$1 \le T \le 5×10^5$，$1 \le K \le 20000$，$1 \le c_i \le 2×10^9$，约定答案不超过 $8×10^{18}$（也就是说，它将适合64位带符号整数）。 #### 题目说明 来源于 [Baltic Olympiad in Informatics 2006](https://www.cs.helsinki.fi/group/boi2006/) 的 [Day 2:City](https://www.cs.helsinki.fi/group/boi2006/tasks/city.pdf)。 由 @[求学的企鹅](/user/271784) 翻译整理。