P7640 [BalticOI 2006] CITY PLANNING (Day 2)

A space station will be built on a planet. The station will employ $N$ people. They must live somewhere, so a city will be built around the station. The land around the station is divided into equal-sized square blocks, and on each block it is possible to build an apartment building with at most $K$ floors. Each building must contain exactly one apartment on each floor, and each person must live in a separate apartment. The space station is located at coordinates $(0,0)$. The other blocks are numbered as shown below:  Because traffic between blocks can only move along streets, the distance from block $(x,y)$ to the space station is $|x|+|y|-1$ units. The cost of building a building equals the sum of the costs of building its floors. As is well known, the cost of building a floor depends only on the floor height, not on the building location. The buildings will be used for $30$ years. The people living in these buildings will commute to the space station for work. Over these $30$ years, transporting one person to and from the station will cost $T \cdot d$, where $d$ is the distance from the person’s building to the space station. We may assume that the planet is large enough and the city occupies only a small part of its surface, so we do not need to consider the curvature of the planet. Your task is to write a program to determine the minimum total cost over $30$ years for building the housing and operating the transportation system.

The first line contains integers $N$, $T$, and $K$. The next $K$ lines specify the construction cost per apartment for each floor. Line $i+1$ contains an integer $c_i$, meaning the cost to build one apartment on the $i$-th floor (assuming all floors below the $(i-1)$-th have already been built). It is well known that building a higher floor is always more expensive than building a lower floor: $c_1

The only line contains one integer: the total cost of building the city and operating the transportation system for $30$ years.

#### Constraints For $100\%$ of the testdata, $1 \le N \le 10^{12}$, $1 \le T \le 5 \times 10^5$, $1 \le K \le 20000$, $1 \le c_i \le 2 \times 10^9$. It is guaranteed that the answer does not exceed $8 \times 10^{18}$ (that is, it fits in a 64-bit signed integer). #### Notes From [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). Translated and organized by @[求学的企鹅](/user/271784). Translated by ChatGPT 5