Minimizing 30‐Year Construction and Transportation Costs

The government of an off‐world colony plans to build a space station at coordinate \( (0,0) \) and hire \(N\) people to work there. Since all employees must live in private apartments, a city will be built on square plots surrounding the station. Each plot may host an apartment building of at most \(K\) floors, and every floor contains exactly one apartment. However, because the station occupies \( (0,0) \), only the other plots (whose coordinates are illustrated in the figure) may be developed.

Due to the layout of the streets, the distance from a plot \( (x,y) \) to the space station is defined as \[ d(x,y)=|x|+|y|-1, \] for any plot \((x,y)\) (note that the plots adjacent to \((0,0)\) have zero travel distance).

The cost to build a building on a plot is the sum of the costs for constructing each individual floor. It is well known that the cost to build a particular floor depends only on the floor’s height. In other words, if the cost to construct the \(i\)th floor is \(c_i\) (given for \(1\le i\le K\)), then building a building with \(m\) floors incurs a cost of \[ S(m)=c_1+c_2+\cdots+c_{m}. \]

Over a 30‐year horizon the station will need to shuttle its residents to and from work. Transportation is provided from the residential buildings to the station at a cost of \(T \cdot d\) per person (where \(d\) is the distance from the building’s plot to \((0,0)\)).

The planners must choose the locations and heights of apartment buildings so that all \(N\) workers get a private apartment while minimizing the overall cost – the sum of all building construction costs and the transportation costs over 30 years. Note that there is an unlimited supply of plots available. However, each building is constrained so that floors must be built sequentially (i.e. one cannot build the \(i\)th floor without building floors \(1, 2, \ldots, i-1\) first).

Task: Given \(N\), \(K\), \(T\) and the cost array \(c_1, c_2, \ldots, c_K\) for constructing individual floors, compute the minimum total cost over 30 years.

Important detail: There are infinitely many plots available. For any plot located at some integer coordinates \((x,y)\) with \((x,y)\neq (0,0)\), its distance is defined by \(d=|x|+|y|-1\). In particular, note that the plots immediately adjacent to \((0,0)\) (e.g. \((1,0)\), \((0,1)\), \((-1,0)\) and \((0,-1)\)) have \(d=0\).

Hint: One way to think about this problem is to consider the marginal cost of assigning an apartment. If a plot at distance \(d\) is chosen, the cost to build its \(i\)th floor is \(c_i+T\cdot d\). However, due to the sequential nature of construction on a plot, the choices are coupled. The problem then becomes one of choosing exactly \(N\) apartments from an infinite set where each available apartment (the \(i\)th floor in a plot at distance \(d\)) has cost \(c_i+T\cdot d\); moreover, there are \(4(d+1)\) plots at distance \(d\) (since all points with \(|x|+|y|=d+1\) are at distance \(d\)).

inputFormat

The first line contains three integers: \(N\) (the number of workers), \(K\) (the maximum number of floors per building), and \(T\) (the transportation cost factor).

The second line contains \(K\) integers \(c_1, c_2, \ldots, c_K\), where \(c_i\) is the cost to construct the \(i\)th floor of any building.

outputFormat

Output a single integer – the minimum total cost (the sum of the construction costs and the 30-year transportation costs) required to house all \(N\) workers.

sample

5 2 10
3 7

19