City Planning

A space station is being built on a planet. The station will employ $N$ people, and they need somewhere to live, so a city is built around the station. The land surrounding the station is divided into equal-sized square lots, and on each lot you may build one apartment building of up to $K$ floors. Each building has exactly one apartment per floor, and every person lives in a separate apartment.

Each lot is assigned coordinates of the form $(x, y)$. The space station is at $(0, 0)$, and the remaining lots are numbered as shown below.

Because traffic can only travel on the streets between lots, the distance between lot $(x, y)$ and the station is $|x| + |y| - 1$.

The cost of building a house equals the sum of the costs of its floors. The cost of building a floor depends only on the height of the floor, not on the location of the building.

The buildings will be used for 30 years. Their residents commute to the station, and transporting one resident to and from the station over these 30 years costs $T \cdot d$, where $d$ is the distance between that resident's building and the station.

The planet is large enough, and the city occupies such a small part of its surface, that the curvature of the surface can be ignored.

Write a program that determines the minimum total cost of building the houses and operating the transportation system for 30 years.

The first line contains the integers $N$ ($1 \le N \le 10^{12}$), $T$ ($1 \le T \le 500,000$), and $K$ ($1 \le K \le 20,000$), separated by spaces.

The next $K$ lines give the cost of building each floor. The $(i + 1)$-th line contains $c_i$ ($1 \le c_i \le 2 \cdot 10^{9}$), the cost of building the $i$-th floor assuming the $i - 1$ floors below it are already built. Building a higher floor always costs more, that is, $c_1 < c_2 < \dots < c_K$.

Print a single integer: the total cost of building the city and operating the transportation system for 30 years. The answer does not exceed $8 \cdot 10^{18}$ and fits in a signed 64-bit integer.