The Space Settlement (city.X)
The cows have discovered a new planet and plan to create a livable
area to which they can "resettle" Farmer John and his hominid ilk.
Thus, the cows are building both a space station and
a settlement of apartment houses that must house N
(1 <= N <= 1,000,000,000,000) people. The settlement's land is partitioned
into equal-sized square lots, each of which may contain an apartment
building with up to K (1 <= K <= 20,000) floors. Each apartment
building has a single apartment on each floor ('a flat') which
houses a single person.
Each lot has coordinates in the form (x, y), where the space station
has coordinates (0, 0), and the rest of the lots are also situated
at integer coordinates. Traffic can only flow on streets between
the lots so the distance of lot (x, y) to the space station is |x|
+ |y| - 1 units.
The apartment buildings must be of quality construction in order
to last 100 years. The cost of constructing an apartment building
is equal to the sum of the costs of building each floor. The cost
to build floor i, c_i (1 <= c_i <= 2,000,000,000), depends on the
height of the floor but not on the location of the building; c_i
is always less than c_i+1 if c_i+1 exists.
People living in the flats work in the space station to which they
commute. Transporting them to and from the station during the 100
years costs T*D (1 <= T <= 500,000) zorkmids per person, where D
is the distance of the person's apartment building from the station.
Write a program that determines the minimal total cost of building
the apartments and operating the transportation system for the 100
years.
PROBLEM NAME: city
INPUT FORMAT:
* Line 1: Three space-separated integers: N, T, and K
* Lines 2..K+1: Line i+1 contains a single integer: c_i
SAMPLE INPUT:
10 20 3
11
22
33
OUTPUT FORMAT:
* Line 1: A single integer that is the minimum total cost to build the
city and to operate the transportation system for 100 years.
The answer will not exceed 8*10^18.
SAMPLE OUTPUT:
194