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