Description

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.

Input Format

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<c_2< \cdots <c_k$.

Output Format

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

17 5 4
100
107
114
121

1778

Hint

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 Day 2:City.
Translated and organized by @求学的企鹅.

Translated by ChatGPT 5